这是 Anouk 上高中的第一天；作为热身活动，体育老师让全班同学玩一个学习名字的游戏。班里共有 $2N$ 名学生。他们大多数人互不相识，但有 $M$ 对好朋友总是形影不离。每名学生最多只有一位好朋友。

老师将所有学生排成一个圆圈，并依次给每名学生分配一个从 $0$ 到 $2N - 1$ 的编号。具体来说，对于每个 $0 \le i < 2N - 1$，学生 $i$ 和 $i + 1$ 站在一起。此外，学生 $0$ 和 $2N - 1$ 也站在一起。

由于老师希望每个人都能结识新同学，好朋友必须尽可能远离对方，即站在彼此的对面。也就是说，第 $i$ 对好朋友分别站在位置 $k_i$ 和 $k_i + N$ 上，其中 $0 \le k_i < N$。

老师选出两名学生 $x$ 和 $y$，并将球交给学生 $x$。目标是将球传给学生 $y$，但每名学生只能将球传给他们已经认识名字的另一名学生。当然，好朋友之间互相认识。在规则讲解过程中，每名学生都认识了站在他们正旁边两名同学的名字。除此之外，没有人认识其他任何人的名字。

游戏共进行 $Q$ 次；老师每次都会选择两名学生。由于学生们没有注意听讲，他们在整个游戏过程中不会学习任何新名字。在每场游戏中，将球从学生 $x$ 传给学生 $y$ 所需的最少传球次数是多少？

输入格式

第一行包含三个整数 $N, M$ 和 $Q$，其中 $2N$ 是 Anouk 班级里的学生人数，$M$ 是好朋友的对数，$Q$ 是进行的游戏次数。

第二行包含 $M$ 个整数 $k_0, \dots, k_{M-1}$，其中 $k_i$ 描述了第 $i$ 对好朋友。对于每个 $i$，好朋友分别站在位置 $k_i$ 和 $k_i + N$ 上。每名学生最多只有一位好朋友。

接下来的 $Q$ 行，每行包含两个整数 $x$ 和 $y$，表示在第 $i$ 场游戏中选出的两名学生。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个整数，表示在第 $i$ 场游戏中所需的最少传球次数。

数据范围

• $2 \le N \le 5 \cdot 10^8$
• $1 \le M \le 5 \cdot 10^5$ 且 $M \le N$
• $1 \le Q \le 2 \cdot 10^4$
• $0 \le k_0 < k_1 < \dots < k_{M-1} < N$
• $0 \le x, y < 2N$ 且 $x \neq y$

子任务

样例

以下两幅图描绘了第一个和第四个样例的排列情况。如果两名学生认识对方的名字，则他们之间有一条边相连。

第一个样例中第一场游戏的最优解

样例 4

在第一个样例的第一场游戏中，球被交给学生 1。学生 1 将球传给他们的好朋友，即学生 5。在学生 5 将球传给学生 4 后，球到达了学生 4，总共需要两次传球。

样例输入 1

4 1 5
1
1 4
1 5
1 7
1 2
1 6

样例输出 1

2
1
2
1
2

样例输入 2

6 1 3
5
5 7
5 1
5 11

样例输出 2

2
3
1

样例输入 3

4 2 4
2 3
0 2
0 3
0 6
0 7

样例输出 3

2
2
2
1

样例输入 4

5 2 5
0 4
0 9
1 8
8 3
1 6
3 9

样例输出 4

1
3
3
3
2

样例输入 5

500000000 4 3
543234 1234566 2300001 249999999
2334445 123567
6578996 12455726
3 269979899

样例输出 5

2210878
5876730
231106567