[AdditionalFile4200.zip](file://AdditionalFile4200.zip?type=additional_file)

#4200. 「ROI 2022 Day1」有趣的周末

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI 2022 Day1 T3. Интересные выходные

彼得和他的弟弟尼古拉来到了水上乐园。尼古拉喜欢玩滑梯，这个滑梯可以被抽象地描述为一个三角形网格的一部分，其顶点就是滑梯的节点。在每个节点，尼古拉可以选择接下来滑向左下或右下。

滑梯的层级从 $0$ 开始上到下编号。在第 $0$ 层，滑梯有一个节点，这个点是旅程的起点；在第 $1$ 层有两个节点……在第 $i$ 层有 $i+1$ 个节点。滑梯总共有 $n+1$ 层。每次从上到下的滑行都会经过 $n$ 个管道。第 $r$ 层从左数第 $c$ 个节点的坐标为 $(r, c)\ (0 \leq c \leq r \leq n)$。注意，层数和每层的节点都是从 $0$ 开始编号的。如果尼古拉在节点 $(r, c)$，并且向左下滑，他将到达节点 $(r + 1, c)$；如果他向右下滑，他将到达节点 $(r + 1, c + 1)$。

以下是一个 $5$ 层水上乐园滑梯的例子：

尼古拉想要滑下滑梯 $n+1$ 次。在每次滑行前，彼得会给他一条如何滑下滑梯的指令。每条指令由 $n$ 个“向左下”或“向右下”的命令组成，指示尼古拉应该从当前节点向哪个方向滑行。

第一条指令只包含“向右下”的命令。彼得懒得想新指令，所以两次连续滑行的指令只有一条命令不同：要从第 $i\ (1 \leq a_i \leq n)$ 条指令得到第 $i+1$ 条指令，需要将第 $a_i$ 条命令从“向右下”改为“向左下”。注意，每条命令都会以这种方式恰好改变一次。最终，第 $n+1$ 条指令将只包含“向左下”的命令。可以证明，尼古拉至少会在一次滑行中访问每个节点。

在从水上乐园返回的路上，尼古拉有了一些这样的问题。对于所有他至少滑行过一次的管道，尼古拉指出两个节点的坐标：$(r_1, c_1)$ 和 $(r_2, c_2)$。你需要确定一个节点 $(r_3, c_3)$ 的坐标，使得从这个节点可以通过这些管道到达节点 $(r_1, c_1)$ 和 $(r_2, c_2)$，并且在所有这样的节点中，节点 $(r_3, c_3)$ 是最低的，即 $r_3$ 的值最大。可以证明，这样的节点总是存在且唯一。

请回答他的所有问题！

输入格式

第一行给出一个整数 $n\ (1 \leq n \leq 5\cdot 10^5)$。

第二行给出 $n$ 个整数 $a_1, a_2, \ldots ,a_n\ (1 \leq a_i \leq n)$，其中 $a_i$ 是第 $i$ 次滑行后将改变的命令的编号。保证所有 $a_i$ 都是不同的。

第三行给出一个整数 $q\ (1 \leq q \leq 5\cdot 10^5)$，表示尼古拉的问题数量。

接下来的q行，每行给出四个整数 $r_{i,1}, c_{i,1}, r_{i,2}, c_{i,2}\ (0 \leq r_{i,1}, r_{i,2} \leq n, 0 \leq c_{i,1} \leq r_{i,1}, 0 \leq c_{i,2} \leq r_{i,2})$，表示第 $i$ 个问题中第一个和第二个节点的坐标。

输出格式

输出 $q$ 行，在第 $i$ 行输出两个整数 $r_{i,3}$ 和 $c_{i,3}$，表示第 $i$ 个问题答案的节点的坐标。

样例

输入

3
2 3 1
5
3 3 3 0
2 2 2 1
1 0 3 1
3 1 3 2
2 2 2 2

输出

0 0
1 1
0 0
2 1
2 2

在第一个样例中，尼古拉的滑行如下所示：

如果标记出尼古拉在第一个示例中滑行过的所有管道，将得到以下结果：

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。