유클리드

데드풀의 식당에서 식사하고 매트릭스에서 탈출한 뒤, 이제 고대 세계로 돌아가 달라는 부탁을 받았습니다. 정확히는 최대공약수가 발명되던 시대입니다.

아름다운 도시 알렉산드리아에는 잔인한 왕이 살고 있습니다. 왕국은 1번부터 N번까지 번호가 붙은 N개의 도시가 일직선 위에 늘어선 형태입니다. 도시 i는 처음에 V_i 코인의 세금을 내야 합니다(1 to N).

왕은 가끔 세금을 올리거나, 주어진 구간의 모든 도시 세금을 나누는 가장 큰 수를 유클리드에게 묻습니다. 초기 배열 V가 주어지며, 이 배열에 대해 Q개의 연산을 처리해야 합니다. 연산은 두 종류입니다.

• query(a, b): gcd(V_a, V_{a+1}, ..., V_b)를 구합니다.
• update(a, b, k): 왕이 세금을 다음과 같이 올립니다. V_a += k, V_{a+1} += 2 × k, ..., V_b += (b - a + 1) × k

첫 줄에 도시 수 N과 연산 수 Q가 주어집니다. 둘째 줄에는 배열 V의 원소 N개가 주어집니다. 이어서 Q개의 줄에 연산이 하나씩 주어집니다.

• 연산이 query(a, b)이면 정수 3개 0 a b가 주어집니다.
• 연산이 update(a, b, k)이면 정수 4개 1 a b k가 주어집니다.

query 연산마다 답을 입력 순서대로 한 줄에 하나씩 출력합니다.

• 1 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000
• 모든 갱신과 질의에 대해 1 ≤ a ≤ b ≤ N
• 모든 갱신에 대해 1 ≤ k ≤ 200,000,000
• 1 ≤ V_i ≤ 200,000,000 (1 ≤ i ≤ N)

첫 번째 연산: gcd(8, 12, 24) = 4.

두 번째 연산 후 배열은 4 12 18 32 66 33 21 7이 됩니다.

세 번째 연산: gcd(12, 18, 32) = 2.