CF331D1 Escaping on Beaveractor

别再忍受你讨厌的事情了！聪明的海狸决定逃离海狸科学学院（BSA）的校园。BSA 是一个位于平面上的 $ b×b $ 正方形区域，每个点 $ (x, y) $ 满足 $ 0 \le x, y \le b $ 都属于校园范围。为了让逃跑过程快捷且有趣，海狸发明了一辆名为“海狸车”的高效舒适交通工具。 校园内遵循严格的交通规则：共有 $ n $ 条箭头线段，这些箭头平行于坐标轴。箭头互不相交也不接触。当海狸车到达某条箭头时，会转向箭头指示的方向继续行驶，直到到达下一条箭头或驶出校园。海狸车每单位时间移动一个单位距离，不会遇到任何障碍。 科学家们计划将这辆全新的海狸车运送到“学术拖拉机”研究所，并让聪明的海狸去攻读研究生，磨练技巧。他们设计了 $ q $ 个计划，包含海狸车的起始位置 $ (x_i, y_i) $，初始行驶方向 $ w_i $，以及从起始位置出发后经过的时间 $ t_i $。 你的任务是对每个计划判断指定时间后，聪明海狸的位置。

第一行包含两个整数：交通规则数量 $ n $ 和校园大小 $ b $，其中 $ 0 \le n $ 且 $ 1 \le b $。接下来 $ n $ 行，每行包含四个空格分隔的整数 $ x_0, y_0, x_1, y_1 $，表示箭头的起点和终点。保证所有箭头都平行于坐标轴且彼此独立，没有交点。所有箭头位于校园内，即 $ 0 \le x_0, y_0, x_1, y_1 \le b $。 随后一行包含一个整数 $ q $，代表科学家的计划数量，$ 1 \le q \le 10^5 $。第 $ i $ 个计划由两个整数 $ x_i, y_i $ 表示海狸车的初始坐标，字符 $ w_i $ 表示初始行驶方向，可以是 'U'（上）、'D'（下）、'L'（左）、'R'（右）（Y 轴向上），以及整数 $ t_i $，表示从起始时间算起经过的时间，$ 0 \le t_i \le 10^{15} $。 - 要获得 30 分，需要解决约束 $ n, b \le 30 $ 的问题（子任务 D1）； - 要获得 60 分，需要解决约束 $ n, b \le 1000 $ 的问题（子任务 D1+D2）； - 要获得 100 分，需要解决约束 $ n, b \le 10^5 $ 的问题（子任务 D1+D2+D3）。

输出 $ q $ 行。每行包含两个整数，表示每个计划中海狸车在指定时间后的坐标。如果聪明的海狸在时间 $ t_i $ 内离开校园，请输出他最后访问并且还在校园内的点的坐标。 **本翻译由 AI 自动生成**