시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 18 8 7 41.176%

문제

N개의 자연수로 이루어진 수열이 있습니다. 이 수열의 연속한 일부분에 일정한 값을 더하는 연산과 연속한 일부분의 최대공약수를 구하는 연산을 수행하는 프로그램을 작성하세요.

입력

첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어집니다. (1 ≤ N ≤ 100,000)

둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어집니다. i번째로 등장한 자연수는 수열의 i번째 원소이며 1 이상 10억 이하의 값을 가집니다.

셋째 줄에 연산의 총 횟수를 나타내는 하나의 자연수 Q가 주어집니다. (1 ≤ Q ≤ 100,000)

넷째 줄부터 Q개의 줄에 걸쳐 각 연산에 대한 정보가 주어집니다. 각 줄에는 T, A, B 3개의 정수가 주어집니다.

T가 0이 아니라면, 수열의 A번째 원소부터 B번째 원소까지에 T라는 수를 더하는 연산입니다.

T가 0이라면, 수열의 A번째 원소부터 B번째 원소까지의 최대공약수를 출력해야 합니다.

T는 0 이상 10억 이하의 값을 가집니다. A와 B는 1 이상 N 이하이며, B는 A보다 크거나 같습니다.

출력

T가 0인 연산이 주어질 때마다 순서대로 각 줄에 해당 연산에서 요구하는 답을 출력합니다.

예제 입력 1

4
6 3 38 49
5
0 1 3
9 2 2
0 1 2
6 3 3
0 3 4

예제 출력 1

1
6
1