Jaemin 居住在一个无限大的矩形网格上。最近，他搬到了一个新的网格，因此目前网格中只有一个障碍物，占据了其中一个单元格。

每个单元格都有一个坐标，定义如下：障碍物位于坐标 $(0, 0)$。如果一个单元格的坐标为 $(x, y)$，那么其右侧的单元格为 $(x + 1, y)$，左侧的单元格为 $(x - 1, y)$，上方的单元格为 $(x, y + 1)$，下方的单元格为 $(x, y - 1)$。

今天，他带着他最喜欢的遥控玩具车来到了这个网格。小车恰好占据网格中的一个单元格。不幸的是，由于这个网格非常大，他忘记了把车放在哪里。在这种情况下，移动小车的唯一方法是按下遥控器上的一个按钮。按下按钮后，小车将尝试执行一条预设的 $N$ 步路径，其中每一步都涉及小车尝试向四个方向之一移动到相邻的单元格。请注意，小车不能进入障碍物所在的单元格；如果小车试图移动到的单元格有障碍物，小车将忽略该指令而不移动，但会继续尝试执行后续的移动。

既然你决定帮助他，他会问你 $Q$ 个问题，形式为：“如果我的小车从 $(x, y)$ 开始，我按下一次按钮，它最终会停在哪里？”你能回答他的问题吗？

输入格式

第一行给出一个整数 $N$，表示指令的长度，其中 $1 \le N \le 300\,000$。

下一行给出小车的预设路径。这是一个长度为 $N$ 的字符串，每个字符分别为 L、R、U 或 D，分别表示小车向左、向右、向上或向下移动。当他按下按钮时，小车会按照上述描述依次执行指令中的每个字符。

下一行给出一个整数 $Q$，表示询问次数，其中 $1 \le Q \le 300\,000$。

接下来的 $Q$ 行，每行给出两个空格分隔的整数 $x$ 和 $y$。小车的起始点为 $(x, y)$。输入满足 $-300\,000 \le x, y \le 300\,000$ 且 $(x, y) \neq (0, 0)$。

输出格式

对于每个询问，输出一行，包含两个由空格分隔的整数 $x$ 和 $y$，表示该询问的答案。

样例

输入 1

8
RRDRUULL
5
-2 1
-2 2
-2 -1
-3 -1
1 1

输出 1

-1 3
-1 3
1 0
-2 -1
2 2