CF331D3 Escaping on Beaveractor

不要忍受你讨厌的事情！聪明的海狸决定从海狸科学学院（BSA）的校园逃离。BSA 是一个平面上的 $b \times b$ 的正方形。每个点 $x, y$（$0 \leq x, y \leq b$）都属于 BSA。为了让逃跑的路线又快又有趣，海狸造了一辆“Beaveractor”，这是一种高效且舒适的交通工具。 校园内有交通规则：有 $n$ 条箭头，且这些箭头与坐标轴平行。箭头之间互不相交，也不接触。当 Beaveractor 到达某个箭头时，它会转向箭头的方向并沿该方向继续前进，直到遇到下一个箭头或离开校园为止。Beaveractor 每单位时间移动一单位距离。你可以认为 Beaveractor 前进的路上没有任何障碍。 BSA 的科学家们想把全新的 Beaveractor 运送到“Academic Tractor”研究所，并让聪明的海狸去那里读研究生和削铅笔。他们有 $q$ 个计划，每个计划给出了 Beaveractor 的初始位置 $(x_{i}, y_{i})$，初始运动方向 $w_{i}$，以及逃跑开始后经过的时间 $t_{i}$。 你的任务是，对于每个计划，计算在给定时间后，聪明的海狸所在的位置。

第一行包含两个整数：交通规则的数量 $n$ 和校园的边长 $b$，$0 \leq n$，$1 \leq b$。接下来的 $n$ 行，每行包含四个用空格分隔的整数 $x_{0}, y_{0}, x_{1}, y_{1}$，表示一条箭头的起点和终点。保证所有箭头都与坐标轴平行且互不相交、互不接触。所有箭头都位于校园内部，即 $0 \leq x_{0}, y_{0}, x_{1}, y_{1} \leq b$。 接下来一行包含整数 $q$，表示科学家们有多少个计划，$1 \leq q \leq 10^{5}$。第 $i$ 个计划由两个整数 $x_{i}, y_{i}$（Beaveractor 的初始坐标，$0 \leq x_{i}, y_{i} \leq b$），一个字符 $w_{i}$（取值为 U、D、L、R，分别表示初始方向为上、下、左、右，Y 轴向上），以及一个整数 $t_{i}$（逃跑开始后经过的时间，$0 \leq t_{i} \leq 10^{15}$）组成。 - 若要获得 30 分，需满足 $n, b \leq 30$（子任务 D1）； - 若要获得 60 分，需满足 $n, b \leq 1000$（子任务 D1+D2）； - 若要获得 100 分，需满足 $n, b \leq 10^{5}$（子任务 D1+D2+D3）。

输出 $q$ 行。每行包含两个整数，表示每个计划在最终时刻 Beaveractor 的坐标。如果聪明的海狸在 $t_{i}$ 时间内离开了校园，则输出他最后一次在校园内停留的点的坐标。

由 ChatGPT 4.1 翻译