Description

Bobo has a sequence p₁, p₂, …, p_n. Initially, p_i = i holds.

One day, Bobo comes up with infinite operations. The operations are described by m pairs of integers (a₁, b₁), (a₂, b₂), …, (a_m, b_m). The i-th operation is to reverse the elements between the a_{(i − 1) mod m + 1}-th and the b_{(i − 1) mod m + 1}-th. Note that a sequence q₁, q₂, …, q_n becomes q₁, …, q_x − 1, q_y, q_y − 1, …, q_x, q_y + 1, …, q_n after reversing the elements between the x-th and the y-th.

Bobo also has q questions k₁, k₂, …, k_q. The i-th question is to ask the number of i satisfying p_i = i if he executes only the first k_i operations. Answer the questions!

• 1 ≤ n ≤ 10⁵
• 1 ≤ m ≤ 10
• 1 ≤ q ≤ 10⁵
• 1 ≤ a_i ≤ b_i ≤ n
• 1 ≤ k_i ≤ 10⁹
• The number of test cases does not exceed 5.

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains three integers n, m and q.

The i-th of the following m lines contains 2 integers a_i and b_i.

The i-th of the last q lines contains an integer k_i.

Output

For each test case, print q integers which denote the answers.

5 1 2
2 4
1
2
5 2 1
1 3
3 5
1000000000

3
5
2

Hint

For the first sample, the sequence becomes 1, 4, 3, 2, 5 after the first operation, and becomes 1, 2, 3, 4, 5 after the second one. Thus, the answer are 3, 5 respectively.