EC_SER - Progression

no tags 

Let S be an infinite sequence of integers:

S0 = a;
S1 = b;
Si = |Si-2 - Si-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^18).

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

The third contains q integers qi.

Output

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

Example

Input:
21 12
5
0 1 2 3 4

Output:
21
12
9
3
6

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


hide comments
:D: 2016-10-02 18:06:42

The trick here is to limit the amount of cases you need to analyze. There are not that many that require encoding if proper reductions are used. Nice problem.

Raghav Aggiwal: 2014-09-28 12:26:58

finally!! easy but requires a lot of analysis .. there will be hell lot of cases..

Last edit: 2014-09-29 16:38:56
wisfaq: 2014-09-05 21:50:58

Dear Eddy, could you please make all your problems available for all languages. I really can't understand why you're keeping to those language restrictions

Last edit: 2014-09-05 21:52:22

Added by:Eddy Cael
Date:2014-09-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Internas UTO 2014