Migrated from Lutece 2727 驱逐摆摆人

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大大超人是卷王。 大大超人讨厌摆烂的废物。 大大超人决定驱逐那些摆烂的摆摆人。

由于大大超人太强了，大大超人的领域可以看做二维平面直角坐标系上的一个边长为 $n$ 等腰直角三角形，其中直角顶点与原点重合，两直角边位于 $x,y$ 正半轴上，即所有满足 $0\le x\le n,0\le y\le n,x+y\le n$的点 $(x,y)$。 开始的时候，大大超人的领域内有 $m$ 个摆摆人，第 $i$ 个摆摆人位于 $(x_i,y_i)$，一个坐标上可以有多个摆摆人。

由于大大超人是神仙，所以他只会用两种方式驱逐摆摆人：

1. 横扫：大大超人运用神力，创造一条端点在 $(0,0),(0,l)$ 的一条神力屏障线段并沿 $x$ 正半轴方向向右推，直到屏障上端点接触到点 $(n-l,l)$，碰到的所有摆摆人会一起被推走（包括屏障线段的端点）。即将位置在 $(x,y)$ 满足 $x<n-l,y\le l$ 的摆摆人驱逐到 $(n-l,y)$（当然原来这个位置可能也有摆摆人）。
2. 竖拍：大大超人运用神力，创造一条端点在 $(0,0),(l,0)$ 的一条神力屏障线段并沿 $y$ 正半轴方向向上推，直到屏障右端点接触到点 $(l,n-l)$，碰到的所有摆摆人会一起被推走（包括屏障线段的端点）。即将位置在 $(x,y)$ 满足 $y<n-l,x\le l$ 的摆摆人驱逐到 $(x,n-l)$（当然原来这个位置可能也有摆摆人）。 由于摆摆人很摆，所以他们自己是永远不会动的。

大大超人的领域里，会依次发生 $q$ 件事，第 $i$ 件事是如下几种事件的一个：

1. 大大超人突发奇想，想知道第 $p_i$ 个摆摆人的坐标。
2. 大大超人创造了一条长度为 $l_i$ 的神力屏障，用横扫驱逐摆摆人。
3. 大大超人创造了一条长度为 $l_i$ 的神力屏障，用竖拍驱逐摆摆人。
4. 有一个新的摆摆人出现在 $(x_i,y_i)$，如果之前已经出现了 $M$ 个摆摆人，则这个摆摆人编号为 $M+1$。

由于大大超人不屑于处理这种简单的事情，所以他将这个任务丢给了你。

Input

第一行输入三个空格隔开的整数 $n,m,q$。 接下来 $m$ 行每行两个空格隔开的整数 $x_i,y_i$ 表示第 $i$ 个摆摆人的坐标。 接下来 $q$ 行每行若干个空格隔开的整数，第一个数 $op\in\{1,2,3,4\}$ 表示四种事件中哪一种。 若 $op=1$，接下来一个整数 $p_i$。 若 $op=2,3$，接下来一个整数 $l_i$。 若 $op=4$，接下来两个整数 $x_i,y_i$。

Output

对于每个 $op=1$ 的事件，输出一行两个整数表示询问的摆摆人的坐标。

Samples

8 1 8
1 5
4 4 1
2 6
1 2
2 3
4 2 2
2 5
1 1
1 3

4 1
3 5
3 2

Constraints

$1\le n\le 10^9,1\le M\le 5\times 10^5,q\le 10^6$。 保证 $0\le x_i,y_i\le n,x_i+y_i\le n$ $0\le l_i\le n-1$ $p_i\le$ 当前摆摆人个数

Resources

2022 UESTC ICPC Training for Data Structures