在遥远的 i1c5l 星球上，一个由 $n$ 个人组成的部落收获了 $k$ 个橙子。现在他们需要分这些橙子。

这个部落根据等级制度的民主原则进行管理。因此，分橙子的方式如下：每个人都会获得一个介于 $1$ 到 $n$ 之间的排名。然后，排名第 $1$ 的人宣布他的决定：谁分到多少个橙子。随后，所有 $n$ 个人投票表决“赞成”或“反对”。如果至少有一半的人投票“赞成”，则该决定被接受。否则，排名第 $1$ 的人将被逐出部落，轮到排名第 $2$ 的人宣布决定，并重复该过程。

每个人都希望为自己争取最大的利益，即尽可能多地获得橙子。在获得的橙子数量相同的情况下，他会倾向于选择部落中剩余人数较少的情况。如果一个人被逐出部落，则认为他获得了负数个橙子。如果存在多个最优解，一个人可以任选其一。每个人都知道其他人也在遵循相同的原则寻找最优解。

然而，部落中的成员之一拥有 $m$ 张万能牌，这些牌可以给他指定排名。任务是找出对于每个万能牌排名，该成员能够获得的最小和最大橙子数量。

输入格式

第一行包含整数 $n$、$k$ 和 $m$（$1 \le n, k \le 10^9$，$1 \le m \le 10^5$），分别表示人数、橙子数和万能牌的数量。

第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \le a_i \le n$），其中 $a_i$ 表示第 $i$ 张万能牌给出的排名。

输出格式

对于每个 $a_i$，在单独的一行中输出万能牌拥有者可以获得的最小和最大橙子数量。如果他/她会被逐出部落，则输出 -1 -1。

样例

输入样例 1

2 10 2
1 2

输出样例 1

10 10
0 0

输入样例 2

3 1 2
1 3

输出样例 2

0 0
1 1

说明

在第一个样例中，排名第一的人拿走了所有的橙子并投了“赞成”票。

在第二个样例中，排名第 $1$ 的人必须把橙子给排名第 $3$ 的人。如果排名第 $1$ 的人自己拿走一个橙子，那么其余成员都会投“反对”票。如果排名第 $1$ 的人把橙子给排名第 $2$ 的人，那么排名第 $2$ 的人也会投“反对”票，因为他知道通过驱逐排名第 $1$ 的人，他同样能得到一个橙子，但部落里剩下的人会更少。由于排名第 $3$ 的人也会投“反对”票，因此这对排名第 $1$ 的人来说不是一个可行的选择。