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

문제

Mr. JOI is working at the IOI Pharmaceutical Co., Ltd. In this company, researchers are busy with experimental work to develop new sterilization sprays.

In this company, the strength of a sterilization spray is defined as follows: when we use a spray of strength x once for a culture plate with y bacteria, the number of bacteria on it becomes ⌊y/x⌋, which is the integer obtained from y/x by rounding off fractions. Now, a new spray of strength K is developed. In order to test the performance of this spray, they plan to experiment on it. They use N culture plates numbered 1, . . . , N. At the beginning, there are Ci bacteria on the culture plate i. In the experiment, they implement Q operations in sequence. Each operation is one of the following:

  • Operation 1: Choose a culture plate a and an integer b, and adjust the number of bacteria on the culture plate a. After this operation, the number of bacteria on the culture plate a becomes b.
  • Operation 2: Choose two integers l,r with 1 ≤ l ≤ r ≤ N. Spray once for each of the culture plates l, l + 1, . . . ,r − 1,r.
  • Operation 3: Choose two integers l,r with 1 ≤ l ≤ r ≤ N. Calculate the sum of the numbers of bacteria on the culture plates l, l + 1, . . . ,r − 1,r, and record it.

Mr. JOI is curious about the results of the experiment assuming that the new spray works as expected. Since you are a good programmer, he asks you to predict the results of the experiment.

Write a program which determines the numbers recorded by the operation 3s in the experiment.

Given the strength of the spray and the information on the operations in the experiment, write a program which determines the numbers recorded by the operation 3s.

입력

Read the following data from the standard input.

  • The first line of input contains three space separated integers N, Q, K. This means the strength of the spray is K, the number of culture plates is N, and the number of operations in the experiment is Q.
  • The i-th line (1 ≤ i ≤ N) of the following N lines contains an integer Ci. This means there are Ci bacteria on the culture plate i at the beginning of the experiment.
  • The i-th line (1 ≤ i ≤ Q) of the following Q lines contains three space separated integers Si, Ti, Ui. They indicate information on the i-th operation in the experiment.
    • When Si = 1, they mean the operation 1 with a = Ti, b = Ui.
    • When Si = 2, they mean the operation 2 with l = Ti, r = Ui.
    • When Si = 3, they mean the operation 3 with l = Ti, r = Ui.

출력

Write the numbers recorded by the operation 3s in the experiment. The number of lines in the output is equal to the number of the operation 3s implemented in the experiment.

제한

All input data satisfy the following conditions.

  • 1 ≤ N ≤ 100 000.
  • 1 ≤ Q ≤ 100 000.
  • 1 ≤ K ≤ 10.
  • 0 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Si ≤ 3 (1 ≤ i ≤ Q).
  • When Si = 1 is satisfied, 1 ≤ Ti ≤ N and 0 ≤ Ui ≤ 1 000 000 000 (1 ≤ i ≤ Q).
  • When Si = 2, 3 is satisfied, 1 ≤ Ti ≤ Ui ≤ N (1 ≤ i ≤ Q).

서브태스크 1 (5점)

  • 1 ≤ N ≤ 3 000
  • 1 ≤ Q ≤ 3 000

서브태스크 2 (10점)

  • Ci ≤ 1 (1 ≤ i ≤ N)
  • When Si = 1 is satisfied, Ui ≤ 1 (1 ≤ i ≤ Q)

서브태스크 3 (10점)

  • K = 1

서브태스크 4 (75점)

There are no additional constraints.

예제 입력 1

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

예제 출력 1

8
3
8
  • At the beginning of the experiment, the numbers of bacteria on the culture plates are 1 2 8 1 3.
  • Adjust the number of bacteria on the culture plate 2 to 5. After this operation, the numbers of bacteria on the culture plates are 1 5 8 1 3.
  • The numbers of bacteria on the culture plates 3, 4, 5 are divided by 3 and rounded off fractions. After this operation, the numbers of bacteria on the culture plates are 1 5 2 0 1.
  • Since the sum of the numbers of bacteria on the culture plates 2, 3, 4, 5 is 8, write 8 to the output.
  • The numbers of bacteria on the culture plates 1, 2, 3, 4 are divided by 3 and rounded off fractions. After this operation, the numbers of bacteria on the culture plates are 0 1 0 0 1.
  • Adjust the number of bacteria on the culture plate 3 to 2. After this operation, the numbers of bacteria on the culture plates are 0 1 2 0 1.
  • Since the sum of the numbers of bacteria on the culture plates 3, 4, 5 is 3, write 3 to the output.
  • Adjust the number of bacteria on the culture plate 2 to 4. After this operation, the numbers of bacteria on the culture plates are 0 4 2 0 1.
  • The numbers of bacteria on the culture plates 1, 2 are divided by 3 and rounded off fractions. After this operation, the numbers of bacteria on the culture plates are 0 1 2 0 1.
  • Adjust the number of bacteria on the culture plate 1 to 4. After this operation, the numbers of bacteria on the culture plates are 4 1 2 0 1.
  • Since the sum of the numbers of bacteria on the culture plates 1, 2, 3, 4, 5 is 8, write 8 to the output.

예제 입력 2

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

예제 출력 2

174
444
76
23
41

채점

  • 예제는 채점하지 않는다.