CF331D2 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 翻译