时空限制

1S/512M

题目描述

在二维坐标系中，一个物品初始位于原点 $(0, 0)$。它按照给定的操作序列进行移动，序列会无限循环执行（即执行完最后一个操作后，立即从第一个操作重新开始）。操作描述如下：

• 每个操作由一个方向 dir 和一个步数 $k$ 组成，记为 dir k。

• dir 是字符类型，取值为 U（往上走，即 y 轴正方向）、D（往下走，即 y 轴负方向）、L（往左走，即 x 轴负方向）或 R（往右走，即 x 轴正方向）。

• $k$ 是一个非负整数，表示向 dir 表示的方向移动的步数。

物品每秒移动一个单位距离，因此每个操作 dir k 需要 $k$ 秒完成（例如，操作 R 3 表示向右移动 $3$ 个单位，耗时 $3$ 秒）。

移动从第 $0$ 秒开始：第 $0$ 秒时物品在 $(0, 0)$，第 $1$ 秒结束时完成第一步移动，以此类推。

现在有 $Q$ 次查询，每次查询给出三个整数 $l, r, t$（$1 \leq l \leq r \leq n$）。对于每个查询，需要临时删除操作序列中第 $l$ 到第 $r$ 个操作，然后计算在删除后的序列循环执行下，第 $t$ 秒结束时物品的坐标 $(x, y)$。

保证删除的区间 $[l, r]$ 不会覆盖整个序列（即 $[l, r] \neq [1, n]$），因此删除后序列至少包含一个操作。

格式

输入格式

第一行包含一个整数 $n$，表示操作序列的长度。

接下来 $n$ 行，每行描述一个操作：一个字符 dir 和一个整数 $k$，格式为 dir k。

接下来一行包含一个整数 $Q$，表示查询次数。

接下来 $Q$ 行，每行描述一个查询：三个整数 $l, r, t$。具体意义见题目描述。

输出格式

对于每个查询，输出一行两个整数 $x$ 和 $y$，表示第 $t$ 秒结束时物品的坐标。

样例

样例输入 #1

4
R 3
U 2
L 1
D 1
3
2 3 8
1 1 5
2 2 4

样例输出 #1

6 -2
-1 2
2 0

数据规模

对于 $30\%$ 的测试数据，$2 \leq n \leq 100$，$1 \leq Q ,k \leq 100$。

对于 $100\%$ 的测试数据，$2 \leq n \leq 10^5$，$1 \leq Q \leq 10^5$，dir $\in$ $\{$U，D，L，R$\}$，$1 \leq k \leq 10^9$，$1 \leq t \leq 10^{18}$，$1 \leq l \leq r \leq n$ 且 $[l,r] \not ={[1,n]}$。