절댓값 수열

시간 제한2초메모리 제한128 MB

요약
앞의 두 항의 절댓값 차로 다음 항을 정의하는 수열에서, 인덱스가 최대 10^18인 질의 최대 50개에 대해 S_i 값을 구하는 문제입니다.
난이도

보통10점 중 6점

유형
정수론, 수학, 시뮬레이션
정답자
아직 제출이 없습니다

문제

길이가 무한한 수열 S를 다음과 같이 정의한다.

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

first, second, 그리고 질문의 개수 N이 주어진다. 각 질문 i에 대해 S_i의 값을 출력하라.

입력

첫째 줄에 first, second, 질문의 개수 N이 주어진다.

둘째 줄부터 N개의 줄에 질문이 하나씩 주어진다. 각 질문은 정수 i이며, 해당 질문의 답은 S_i이다.

N은 50 이하의 자연수이다. first, second, 모든 질문 i는 10^18 이하의 음이 아닌 정수이다.

출력

각 질문에 대한 S_i를 입력 순서대로 한 줄에 하나씩 출력한다.

예제4

  1. 예제 1

    입력
    21 12 5
0
1
2
3
4
    예상 출력
    21
12
9
3
6

  2. 예제 2

    입력
    0 0 1
1000000000000000000
    예상 출력
    0

  3. 예제 3

    입력
    823 470 10
3
1
31
0
8
29
57
75
8
77
    예상 출력
    117
470
2
823
115
87
49
25
115
23

  4. 예제 4

    입력
    710370 177300 10
5
95
164721
418
3387
710
0
1197
19507
5848
    예상 출력
    178470
108270
90
0
90
90
710370
90
0
0