样例下载

题目描述

蚂蚁王国有 $N$ 条道路，这些道路全部是水平的或竖直的。

我们将蚂蚁王国看作是一个二维平面，它的每条道路都看作是一条平行于 $x$ 轴或 $y$ 轴的无限长的直线。

有 $M$ 只蚂蚁，初始时，第 $i$ 只蚂蚁正位于整点 $(x_i, y_i)$ 处。每只蚂蚁的行走路线都有严格的规则：

1、蚂蚁只会向 $x$ 轴或 $y$ 轴的正方向行走，每秒钟行走一个单位距离。

2、如果蚂蚁正行走在道路上，则下一秒它会沿着行走方向继续前进。

3、如果蚂蚁位于两条道路的交叉口，假如此时蚂蚁已经行走了偶数秒，则下一秒它会向 $y$ 轴的正方向继续前进；如果已经行走了奇数秒，则下一秒它会沿着 $x$ 轴的正方向继续前进。

问：对于第 $i$ 只蚂蚁，经过 $t_i$ 秒之后，它的位置在哪里？

输入格式

第一行：两个整数 $N, M$。

接下来 $N$ 行，每行描述一条道路：每行首先是一个小写字母 $x$ 或 $y$，接着是一个整数 c，表示这条道路是直线 $x=c$ 或 $y=c$。数据保证不会存在重叠的两条直线。

接下来 $M$ 行，每行描述一只蚂蚁，包含三个整数 $x_i, y_i, t_i$。数据保证 $(x_i, y_i)$ 一定位于前面给出的直线道路上。

输出格式

共 $M$ 行，每行两个整数 $x, y$，其中第 $i$ 行表示第 $i$ 只蚂蚁所求位置的坐标。

输入样例

4 4
x 7
y 4
y 5
x 6
6 3 10
6 4 10
6 5 10
6 6 10

输出样例

14 5
7 13
6 15
6 16

样例解释

第一只蚂蚁的路线：

$(6, 3) \to (6, 4) \to (7, 4) \to (7, 5) \to (8, 5) \to \ldots \to (14, 5)$

第二只蚂蚁的路线：

$(6, 4) \to (6, 5) \to (7, 5) \to (7, 6) \to \ldots \to (7, 13)$

其他蚂蚁的路线略。

数据范围

• 10% 的数据：$N,M,c,x_i,y_i,t_i ≤ 200$。
• 40% 的数据：$N,M ≤ 3000$。
• 100% 的数据：$1 ≤ M ≤ 2·10^5$; $1 ≤ N ≤ 2·10^5$; $0 ≤ c ≤ 10^9$; $0 ≤ x_i, y_i, t_i ≤ 10^9$