Memory Names Passing Game

On the first day at Anouk High School, as a warm‐up activity, the physical education teacher organized a name memory game. There are \(2N\) students arranged in a circle with positions from \(0\) to \(2N - 1\). For each \(0 \le i < 2N-1\), student \(i\) stands next to \(i+1\), and additionally, student \(0\) is adjacent to student \(2N-1\).

Among these students, most do not know each other except for \(M\) pairs of best friends. Each student has at most one best friend, and if a pair is best friends then they must stand as far apart as possible: they are placed diametrically opposite; formally, for the pair associated with some integer \(k\) (with \(0 \le k < N\)), the two best friends stand at positions \(k\) and \(k+N\).

The teacher selects two students \(x\) and \(y\) and gives a ball to student \(x\). The goal is to pass the ball to student \(y\). However, a student can only pass the ball to someone whose name they already know. Initially, every student knows the names of the two adjacent students in the circle. In addition, best friends know each other’s names. The game is played \(Q\) times with different choices of \(x\) and \(y\) (and the knowledge remains the same across games).

Your task is to determine the minimum number of passes needed to get the ball from \(x\) to \(y\) in each game.

Note

The circle distance between two positions \(a\) and \(b\) is defined as \(\min(|a - b|, 2N - |a - b|)\). If a student has a best friend, denote it as \(f(u)\) (i.e. if \(u < N\) and \(u\) is in one of the best friend pairs then \(f(u) = u+N\); if \(u \ge N\) and \(u-N\) is in the best friend pairs then \(f(u)= u-N\)).

Hints

• The direct route using only circle-adjacent passes takes \(\text{circle}(x, y)\) passes.
• If \(x\) has a best friend, one can consider the route: \(x \to f(x)\) then circle to \(y\), costing \(1 + \text{circle}(f(x), y)\) passes.
• If \(y\) has a best friend, the route \(x \to f(y) \to y\) takes \(1 + \text{circle}(x, f(y))\) passes.
• If both have best friends, another option is \(x \to f(x)\) then circle to \(f(y)\) then \(f(y) \to y\), costing \(2 + \text{circle}(f(x), f(y))\) passes.

The answer is the minimum over all valid routes.

inputFormat

The first line contains three integers \(N\), \(M\), and \(Q\) where \(2N\) is the number of students, \(M\) is the number of best friend pairs, and \(Q\) is the number of games played.

If \(M > 0\), the second line contains \(M\) distinct integers \(k\) (each satisfying \(0 \leq k < N\)). Each such \(k\) represents a best friend pair consisting of students at positions \(k\) and \(k+N\). If \(M = 0\), the second line will be empty.

The following \(Q\) lines each contain two integers \(x\) and \(y\) (\(0 \le x,y < 2N\)), representing a game where the ball is passed from student \(x\) to student \(y\).

outputFormat

For each game, output a single integer representing the minimum number of passes required to get the ball from student \(x\) to student \(y\).

sample

3 1 3
1
0 2
1 4
5 3

2
1
2

</p>