不要忍受你已经厌倦的事情!聪明的海狸决定逃离海狸科学院(BSA)的校园。 BSA 是平面上的 b × b 正方形。每个点 x, y (0 ≤ x, y ≤ b) 都属于 BSA。为了使路径变得快速而有趣,海狸建造了 Beaveractor,这是一种有效且舒适的交通工具。
校园遵守交通规则:有n个箭头,与坐标轴平行。箭头不相交,也不互相接触。当海狸演员到达某个箭头时,它会沿着箭头的方向转向并继续前进,直到到达下一个箭头或到达校园外。 Beaveractor 每一个单位时间恰好覆盖一个单位空间。您可以假设海狸演员没有任何障碍。
BSA 科学家希望将全新的 Beaveractor 运送到“学术拖拉机”研究所,并派 Smart Beaver 进行研究生学习和削铅笔。他们有 q 个计划,代表 Beaveractor 的初始位置 (xi, yi)、初始运动矢量 wi 以及逃跑开始后经过的时间 ti。
您的任务是为每个 q 计划确定智能海狸在给定时间后的位置。
输入
第一行包含两个整数:交通规则数量n和校园规模b,0≤n,1≤b。接下来的 n 行包含规则。规则的每一行包含四个空格分隔的整数 x0、y0、x1、y1——箭头的开头和结尾。保证所有箭头与坐标轴平行且没有公共点。所有箭头均位于校园内,即 0 ≤ x0, y0, x1, y1 ≤ b 成立。
下一行包含整数 q — 科学家有的计划数量,1 ≤ q ≤ 105。第 i 个计划由两个整数表示,xi, yi 是 Beaveractor 在初始时间的坐标,0 ≤ xi, yi ≤ b,字符 wi,取值 U、D、L、R 并相应设置初始方向向上、向下、向左或向右(Y 轴)向上),ti — 逃生开始后经过的时间,0 ≤ ti ≤ 1015。
- 要获得 30 分,您需要解决约束为 n, b ≤ 30 的问题(子问题 D1);
- 要获得 60 分,您需要解决约束为 n, b ≤ 1000 的问题(子问题 D1+D2);
- 要获得 100 分,您需要解决约束为 n, b ≤ 105 的问题(子问题 D1+D2+D3)。
输出
打印 q 行。每行应包含两个整数 - 每个计划的最后时刻海狸演员的坐标。如果智能海狸设法在 ti 时间内离开校园,则打印他访问过的校园中最后一个点的坐标。
示例
输入 #1
3 3 0 0 0 1 0 2 2 2 3 3 2 3 12 0 0 L 0 0 0 L 1 0 0 L 2 0 0 L 3 0 0 L 4 0 0 L 5 0 0 L 6 2 0 U 2 2 0 U 3 3 0 U 5 1 3 D 2 1 3 R 2
输出 #1
0 0 0 1 0 2 1 2 2 2 3 2 3 2 2 2 3 2 1 3 2 2 1 3