404245: GYM101466 J Jeronimo's List

Jeronimo the bear loves numbers and he is planning to write n numbers in his notebook.

After writing the first m numbers, Jeronimo felt that he was spending a lot of time thinking new numbers, so he wrote the next n - m missing numbers as the sum modulo 3 × 10⁷ of the numbers in the i - m and i - m + 1 positions for m < i ≤ n

While Jeronimo was writing, his sister Lupe arrived and asked him q questions. The i - th question consist of a number b_i, Jeronimo has to say what would be the number in the position b_i if all the numbers were sorted in ascending order. Jeronimo wants to answer each question as soon as possible but he spends a lot of time counting so he ask your help.

The first line of the input has three integers n (3 ≤ n ≤ 3 × 10⁷), m (3 ≤ m ≤ min(100, n)) and q (1 ≤ q ≤ 10000).

The second line contains m numbers a₁, a₂, ..., a_m, (0 ≤ a_i < 3 × 10⁷), The first m numbers that Jeronimo wrote.

The third line contains q questions b₁, b₂, ..., b_q (1 ≤ b_i ≤ n)

Print q lines. The i - th line must be the answer of the i - th question made by Lupe.

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

1
2
3
3
5
6

10 4 3
1 2 9 10
1 5 10

1
10
30