← 返回题目列表

Codeforces · 331/D1

D1. 乘坐海狸演员逃跑

中文机器翻译题面 查看原题

不要忍受你已经厌倦的事情!聪明的海狸决定逃离海狸科学院(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