NC207600. StarMap

描述

Alice喜欢星空，她的朋友拍摄了一张星空的照片送给她。
Alice将照片放到一个平面直角坐标系中，由此可以确定所有光点的坐标，并给它们编号。
Alice会依照编号顺序从1到m告诉你每个光点的坐标。
她会将照片以坐标原点为中心缩放，以坐标原点为旋转轴旋转，或是将照片平移。

她会告诉你n个操作，并向你问q个问题。

每个操作符合以下三者之一：
1 p，表示对照片以坐标原点为中心缩放。形式化地说，如果p为正值，表示放大，所有坐标都会变成。如果p为负值，表示缩小，所有坐标都会变成。
2 ，表示对照片以坐标原点为中心逆时针旋转度（角度制）。Alice向你保证，只可能是0、90、180、270。
3 ，表示对照片进行平移。所有坐标都会移动到。

每个问题遵循以下规则：

l r t，表示如果只对初始照片从第l个操作开始，执行到第r个操作（包含第l个和第r个操作），询问编号为t的光点的坐标此时为多少。

输入描述

第一行输入三个正整数m、n、q。
接下来m行，每行输入两个整数x、y，按照光点编号顺序依此输入该光点的坐标。
接下来n行，每行输入一个操作，形式在题目描述中给出。
接下来q行，每行输入三个正整数l、r、t，表示此次询问的内容。

数据规范：
* 
* 
* 
* 
* 
* ，其中|x|表示取x的绝对值
* 

输出描述

对于每个询问，输出两个整数x和y，之间使用一个空格符分隔，表示当前询问的光点的坐标，每个询问的答案占一行。

注意：为了避免计算误差，如果询问结果的坐标为，你只需要输出和，其中表示取余，即模算术。如果你需要用到除法，则需要通过乘上除数的模逆元来完成，即对于，你需要计算，其中称作q在模数20090909下的模逆元，它满足性质。

示例1

输入:

1 3 6
2 3
1 2
2 90
3 1 1
1 1 1
1 2 1
1 3 1
2 2 1
2 3 1
3 3 1

输出:

4 6
20090903 4
20090904 5
20090906 2
20090907 3
3 4

原站题解