Absolute Value Sequence

Time limit2sMemory limit128 MB

Summary
Given the first two terms of a sequence where each later term is the absolute difference of the two before it, answer up to 50 queries for S_i with i as large as 10^18.
Level

Medium6 of 10

Topics
Number theory, Math, Simulation
Solved
No attempts yet

Problem

An infinite sequence S is defined as follows.

  • S_0 = first
  • S_1 = second
  • S_i = |S_{i-2} - S_{i-1}| for i >= 2

You are given first, second, and the number of queries N. For each query index i, output the value of S_i.

Input

The first line contains first, second, and the number of queries N.

Each of the next N lines contains one query. A query is an integer i, and its answer is S_i.

N is a positive integer no greater than 50. first, second, and every query index i are non-negative integers no greater than 10^18.

Output

For each query, output S_i on its own line, in the same order as the input queries.

Examples4

  1. Example 1

    Input
    21 12 5
0
1
2
3
4
    Expected output
    21
12
9
3
6

  2. Example 2

    Input
    0 0 1
1000000000000000000
    Expected output
    0

  3. Example 3

    Input
    823 470 10
3
1
31
0
8
29
57
75
8
77
    Expected output
    117
470
2
823
115
87
49
25
115
23

  4. Example 4

    Input
    710370 177300 10
5
95
164721
418
3387
710
0
1197
19507
5848
    Expected output
    178470
108270
90
0
90
90
710370
90
0
0