시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 1 1 33.333%

문제

길이가 n인 수열 A0, A1, ..., An-1이있다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 l r c: l ≤ i ≤ r에 속하는 모든 Ai에 c를 더한다.
  • 2 l r d: l ≤ i ≤ r에 속하는 모든 Ai를 ⌊Ai/d⌋로 바꾼다.
  • 3 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 가장 작은 값을 출력한다.
  • 4 l r: l ≤ i ≤ r에 속하는 모든 Ai의 합을 출력한다.

⌊x⌋는 y ≤ x를 만족하는 가장 큰 정수 y이다. (⌊-2.5⌋ = -3, ⌊-7⌋ = -7)

입력

첫째 줄에 수열의 크기 n과 쿼리의 개수 q (1 ≤ n, q ≤ 100,000)가 주어진다.

둘째 줄에는 A0, A1, ..., An-1가 주어진다. (-109 ≤ Ai ≤ 109)

다음 q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (0 ≤ l ≤ r ≤ n-1, -104 ≤ c ≤ 104, 2 ≤ d ≤ 109)

출력

3번 4번 쿼리가 주어질 때 마다 정답을 한 줄에 하나씩 출력한다.

예제 입력

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

예제 출력

-2
-2
-2
-2
0
1
1

힌트

출처