描述

C国和J国开战了。

你是C国的指挥官，现在前线传来了一份地形图。

地形图是一个在二维平面上的一个多边形。

设它的顶点是：(x0,y0),(x1,y1)...(xn-1,yn-1)，相邻两顶点有边，第n个顶点和第1个顶点有边。

情报人员对地形图进行了加密：
加密之后仍然用n个点表示:(ax0,ay0),(ax1,ay1)...(axn-1,ayn-1)
其中第i个点表示第i条边的中点:
2*axi = xi + x(i+1), 2*ayi = yi + y(i+1), 2*axn-1 = xn-1 + x0, 2*ayn-1 = yn-1 + y0
这样，通过加密后的信息我们就可以得出原图形的顶点坐标了（在大多数情况下）。

现在有三种操作：
1、Q p 查询(xp, yp)的坐标值，如果该多边形不存在，则输出-1，如果有无穷多个坐标，则输出-2
2、D p 将(axp, ayp)删除，其后的点前移一个位置，相当于原多边形减少了一个顶点。

3、I p x y 插入一个中点，坐标为(x, y)，插入到p号位置,原来(p~n-1)的点后移一个位置，相当于原多边形增加一个顶点。

你能准确的得出需要查询的顶点坐标吗？

格式

输入格式

第一行，n,q分别表示初始顶点数，操作数
第二行，2n个正整数，表示n个中点的坐标
接下来q行：
首先一个操作符C:
若C为'Q'，则接下来一个整数，表示询问的点的编号
若C为'D'，则接下来一个整数，表示删除的点的编号
若C为'I',则接下来三个整数，表示插入的位置及坐标
保证读入合法，即设当前有m个点，
则询问的编号在0~m-1之间，删除的编号在0~m-1之间，插入的点的位置在0~m之间

输出格式

对于每一个Q，
如果不存在合法多边形，输出-1
如果坐标有无穷多组解，输出-2
否则输出两个整数，表示坐标(x,y)

样例1

样例输入1

3 10
0 1 1 0 1 1
Q 0
Q 1
Q 2
D 2
D 1
I 0 -1 0
I 0 -1 1
Q 0
Q 1
Q 2

样例输出1

0 2
0 0
2 0
0 2
-2 0
0 0

样例2

样例输入2

4 1
0 1 1 0 2 1 1 2
Q 0

样例输出2

-2

样例3

样例输入3

10 10
1379 39
-525 1609
1035 -109
-1645 -792
-408 -1762
-1213 1044
120 654
-1937 -1691
-346 -1393
1594 -1719
Q 4
I 4 518 -1608
Q 10
Q 3
I 10 -271 -1430
D 4
D 4
D 4
Q 3
D 6

样例输出3

-1
-992 -1078
1698 -998
-2282 -3134

限制

每个测试点1s

提示

多边形是任意的多边形（可以自交，点可以重叠，边可以共线，可以退化成一个点，一条线）
1-3：只有Q操作，n <= 100, q <= 100
4-5：只有Q操作，n <= 10000, q <= 5000
6-8：n <= 1000, q <= 1000
9-10：n <= 50000, q <= 50000
保证读入的坐标范围在[-2000,2000],保证删除操作之后至少有两个点，保证n>=2

温馨提示：暴力可以得很多分

来源

原创(by pty, zzx)
如有雷同，纯属巧合