Let S be an infinite sequence of integers:

S₀ = a;
S₁ = b;
S_i = |S_i-2 - S_i-1| for all i ≥ 2.

You have two integers a and b. You must answer some queries about the n-th element in the sequence

Input

The first line contains a and b (0 ≤ a, b ≤ 10¹⁸).

The second line contains a integer q (1 ≤ q ≤ 100000).

The third contains q integers q_i.

Output

For each q_i you must print a line with the q_i-th element of S.

Example

Input:
21 12
5
0 1 2 3 4
Output:
21
12
9
3
6

Note: the values of q_i are in the range of 64 bits.