Byteasar 是一名在箭洞（Arrow Cave）工作的护林员，这里是情侣们著名的约会地点。该洞穴由 $n$ 个房间组成，房间之间由单向走廊连接。在每个房间中，恰好有一条标有箭头的出口走廊。每条走廊都直接通向某个（不一定不同）房间。

约定在箭洞会面的情侣们经常因为忘记商定具体的房间而无法找到对方。过去，这导致了许多混乱和误解……但自从每个房间都配备了通往值班护林员的紧急电话线后，帮助情侣们找到彼此就成了护林员的主要工作。

护林员们想出了以下方法：在知道情侣们所在位置后，他们会告诉每人需要沿着标有箭头的走廊走多少次才能与对方会合。情侣们显然希望尽快见面——毕竟，他们来到洞穴是为了共度时光，而不是独自徘徊！大多数护林员都很乐意效劳：他们会尽力为每对情侣提供一对有效的数字，使得它们的最大值最小。

但一些护林员，包括 Byteasar 在内，对这种课外活动及其带来的难题感到厌倦。Byteasar 请你编写一个程序来简化这个过程。该程序在给定洞穴描述和 $k$ 对情侣当前位置的情况下，应确定 $k$ 对数字 $x_i$ 和 $y_i$，使得：

• 如果第 $i$ 对情侣分别沿着标有箭头的走廊走了 $x_i$ 次（男方）和 $y_i$ 次（女方），他们将在洞穴的同一个房间会合，
• $\max(x_i, y_i)$ 最小，
• 在满足上述条件的前提下，$\min(x_i, y_i)$ 最小，
• 如果上述条件仍不能确定唯一解，则女方应走较短的距离（即 $x_i \ge y_i$）。

如果这样的数字 $x_i$ 和 $y_i$ 不存在，则令 $x_i = y_i = -1$。注意，多对情侣在同一个房间会合是可以的。一旦情侣们找到了对方，他们就会很高兴地再次消失在洞穴中……

输入格式

第一行包含两个正整数 $n$ 和 $k$（$1 \le n \le 500,000$，$1 \le k \le 500,000$），用空格分隔，分别表示箭洞中房间的数量和想要寻找对方的情侣对数。房间编号从 $1$ 到 $n$，情侣编号从 $1$ 到 $k$。

第二行包含 $n$ 个正整数，用空格分隔：第 $i$ 个整数表示从房间 $i$ 出发的标有箭头的走廊所通向的房间编号。

接下来的 $k$ 行指定了每对情侣的查询。每行包含两个正整数，用空格分隔，分别表示男方和女方所在的房间编号。

在总分占比 $40\%$ 的测试点中，满足 $n \le 2,000$ 且 $k \le 2,000$。

输出格式

你的程序应向标准输出打印恰好 $k$ 行，每对情侣对应一行：第 $i$ 行应给出第 $i$ 对情侣的指令，即包含两个用空格分隔的整数 $x_i$ 和 $y_i$。

样例

输入 1

12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5

输出 1

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