题目描述

某城市地铁一号线共有 $n$ 个车站，按顺序编号为 $1 \sim n$。

地铁的计费规则如下：

• 线路被划分成 $k$ 个不重不漏的「收费区」，每个收费区包含若干连续车站。
• 在同一车站进出，收费 $1$ 元。
• 起点和终点在同一收费区内的不同车站，收费 $2$ 元。
• 否则，设起点和终点之间恰好完整包含了 $m$ 个收费区，则收费 $2 + m$ 元。具体地，设端点车站为 $a,b~(a\lt b)$，满足 $a\le l_x \le r_x \le b$ 的收费区 $x$ 的数量即为 $m$，其中 $l_x,r_x$ 是收费区 $x$ 的左右端点。

收费区的定义：给出 $k + 1$ 个分界点 $1=p_0 \lt p_1\lt p_2\lt \ldots\lt p_k=n+1$，则第 $i$ 个收费区包含所有满足 $p_{i-1}\le x\lt p_i$ 的车站 $x$，即 $l_i=p_{i-1}$，$r_i=p_i-1$。

回答 $q$ 次询问，每次给出两个车站编号，求车费。

输入格式

第一行两个由空格分隔的正整数 $n,k$。

第二行 $k+1$ 个由空格分隔的正整数，表示分界点。第 $i$ 个正整数表示 $p_{i-1}$。

第三行一个整数 $q$。

接下来 $q$ 行，每行输入两个正整数 $i,j$，表示一次询问。

输出格式

对于每组询问，输出一行一个整数表示答案。

样例

10 4
1 3 5 7 11
6
2 2
1 3
1 4
10 1
6 9
3 4

1
3
4
6
2
2

5 5
1 2 3 4 5 6
3
1 1
1 3
2 5

1
5
6

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

3
2
1
4
2

提示

样例 1 解释

$10$ 个车站划分为 $4$ 个收费区：

• 收费区 $1$：车站 $1,2$。
• 收费区 $2$：车站 $3,4$。
• 收费区 $3$：车站 $5,6$。
• 收费区 $4$：车站 $7,8,9,10$。

数据范围与约定

$1\le k\le 1000, 1\le n\le 10^9, k\le n, 1\le q\le10^5$。

特殊性质 A：$k=n$。

特殊性质 B：$k=2$。

特殊性质 C：$n$ 是 $k$ 的倍数且所有收费区大小相等。