12858번 - Range GCD

문제

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인 연산은 하나 이상 주어진다.

출력

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

제한

힌트