CF331D3.Escaping on Beaveractor

Don't put up with what you're sick of! The Smart Beaver decided to escape from the campus of Beaver Science Academy (BSA). BSA is a b × b square on a plane. Each point x, y (0 ≤ x, y ≤ b) belongs to BSA. To make the path quick and funny, the Beaver constructed a Beaveractor, an effective and comfortable types of transport.

The campus obeys traffic rules: there are n arrows, parallel to the coordinate axes. The arrows do not intersect and do not touch each other. When the Beaveractor reaches some arrow, it turns in the arrow's direction and moves on until it either reaches the next arrow or gets outside the campus. The Beaveractor covers exactly one unit of space per one unit of time. You can assume that there are no obstacles to the Beaveractor.

The BSA scientists want to transport the brand new Beaveractor to the "Academic Tractor" research institute and send the Smart Beaver to do his postgraduate studies and sharpen pencils. They have q plans, representing the Beaveractor's initial position (x__i, y__i), the initial motion vector w__i and the time t__i that have passed after the escape started.

Your task is for each of the q plans to determine the Smart Beaver's position after the given time.

别再忍受你厌烦的一切了！聪明的海狸决定逃离河狸科学学院（BSA）的校园。BSA 是平面上一个边长为 $b$ 的正方形区域，其中所有满足 $0 \le x, y \le b$ 的点 $(x, y)$ 均属于 BSA。为了使逃逸路径既快捷又有趣，海狸建造了一台“海狸机”（Beaveractor）——一种高效且舒适的交通工具。

校园内实行交通规则：共有 $n$ 个箭头标记，均平行于坐标轴。这些箭头互不相交，也互不接触。当海狸机抵达某个箭头时，它会立即转向该箭头所指示的方向，并沿此方向持续移动，直至抵达下一个箭头或驶出校园边界。海狸机每单位时间恰好移动一个单位距离。你可以假定海狸机在行进过程中不会遇到任何障碍。

BSA 的科学家们计划将这台崭新的海狸机运往“学术拖拉机”研究所，并安排聪明的海狸前往攻读研究生学位、削铅笔。他们共制定了 $q$ 种运输方案，每种方案包含海狸机的初始位置 $(x_i, y_i)$、初始运动方向向量 $w_i$，以及自逃逸开始后经过的时间 $t_i$。

你的任务是：对这 $q$ 种方案中的每一种，计算并输出聪明的海狸在给定时间 $t_i$ 后所处的位置。

The first line contains two integers: the number of traffic rules n and the size of the campus b, 0 ≤ n, 1 ≤ b. Next n lines contain the rules. Each line of the rules contains four space-separated integers _x_0, _y_0, _x_1, _y_1 — the beginning and the end of the arrow. It is guaranteed that all arrows are parallel to the coordinate axes and have no common points. All arrows are located inside the campus, that is, 0 ≤ _x_0, _y_0, _x_1, _y_1 ≤ b holds.

Next line contains integer q — the number of plans the scientists have, 1 ≤ q ≤ 105. The i-th plan is represented by two integers, x__i, y__i are the Beaveractor's coordinates at the initial time, 0 ≤ x__i, y__i ≤ b, character w__i, that takes value U, D, L, R and sets the initial direction up, down, to the left or to the right correspondingly (the Y axis is directed upwards), and t__i — the time passed after the escape started, 0 ≤ t__i ≤ 1015.

• to get 30 points you need to solve the problem with constraints n, b ≤ 30 (subproblem D1);
• to get 60 points you need to solve the problem with constraints n, b ≤ 1000 (subproblems D1+D2);
• to get 100 points you need to solve the problem with constraints n, b ≤ 105 (subproblems D1+D2+D3).

第一行包含两个整数：交通规则的数量 $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$（表示 Beaveractor 在初始时刻的坐标，满足 $0 \le x_i,\,y_i \le b$）、一个字符 $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）。

Print q lines. Each line should contain two integers — the Beaveractor's coordinates at the final moment of time for each plan. If the Smart Beaver manages to leave the campus in time t__i, print the coordinates of the last point in the campus he visited.

输出 q 行。每行应包含两个整数——即每个计划下 Beaveractor 在最终时刻的位置坐标。若 Smart Beaver 能在时间 t__i 内离开校园，则输出他在校园内访问的最后一个点的坐标。