You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

星际航线

题目背景

无。

题目描述

在一个星系里有 $2n$ 个空间站，这些空间站排成一个环形，分别编号为 $0,1,...,2n-1$ 。相邻编号的两个空间站有直达的星际航线，特别地， $0$ 号空间站和 $2n-1$ 号空间站是相邻的，它们之间也有星际航线。

但是，这样的航线图引来了很多空间站居民的不满，因为相对的两个空间站的距离实在是太远了。为了方便居民出行，空间站新建了 $m$ 条航线，第 $i$ 条航线连接的是 $k_i$ 号空间站和 $k_i+n$ 号空间站 $(0\le k_i<n)$。由于这些星际航线都是采用虫洞技术来建设的，因此穿越每一条航线的时间都相等，为 $1$ 单位时间。

现在有 $q$ 位居民需要出行， 第 $j$ 位居民要从 $x_j$ 号空间站到 $y_j$ 号空间站，请你计算出每位居民出行所需的最短时间。

输入格式

输入的第一行包含三个整数$n,m,q$，第二行包含 $m$ 个整数 $k_1 ,\cdots, k_{m}$，接下来的 $q$ 行每行包含两个整数 $x_j$ 和 $y_j$。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，即第 $i$ 位居民出行所需的最短时间。

样例 #1

样例输入 #1

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

样例输出 #1

2
1
2
1
2

样例 #2

样例输入 #2

6 1 3
5
5 7
5 1
5 11

样例输出 #2

2
3
1

样例 #3

样例输入 #3

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

样例输出 #3

2
2
2
1

样例 #4

样例输入 #4

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

样例输出 #4

1
3
3
3
2

样例 #5

样例输入 #5

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

样例输出 #5

2210878
5876730
231106567

提示

样例解释

第一个样例的第一个居民从 $1$ 号空间站出发，先通过新建的航线到 $5$ 号空间站，再通过原来的航线到 $4$ 号空间站，总共需要 $2$ 单位时间。

数据范围

对于全部数据，$2\le n\le 5\times 10^8$，$1\le m\le 5\times 10^5$ 且 $m\le n$，$1\le q\le 2\times 10^4$，$0\le k_1<\cdots<k_{m}<n$，$0\le x_j,y_j < 2n$ 且 $x_j\ne y_j$。

• 子任务一（$14$ 分）：$m=1$ 且 $x_i=k_0$。
• 子任务二（$20$ 分）：$n,m,q\le 1000$。
• 子任务三（$22$ 分）：$n\le 10^7$ 且 $m,q\le 1000$。
• 子任务四（$17$ 分）：$x_i=0$。
• 子任务五（$27$ 分）：无特殊限制。