Description

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 $\lfloor y/x \rfloor$, 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, \dots, N$. At the beginning, there are $C_i$ 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 \leq l \leq r \leq N$. Spray once for each of the culture plates $l, l+1, \dots, r-1, r$.
• Operation 3: Choose two integers $l, r$ with $1 \leq l \leq r \leq N$. Calculate the sum of the numbers of bacteria on the culture plates $l, l+1, \dots, 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.

Task

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.

Input Format

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 \leq i \leq N$) of the following $N$ lines contains an integer $C_i$. This means there are $C_i$ bacteria on the culture plate $i$ at the beginning of the experiment.
• The $i$-th line ($1 \leq i \leq Q$) of the following $Q$ lines contains three space separated integers $S_i, T_i, U_i$. They indicate information on the $i$-th operation in the experiment.
  • When $S_i = 1$, they mean the operation 1 with $a = T_i, b = U_i$.
  • When $S_i = 2$, they mean the operation 2 with $l = T_i, r = U_i$.
  • When $S_i = 3$, they mean the operation 3 with $l = T_i, r = U_i$.

Output Format

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.

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

8
3
8

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

174
444
76
23
41

Hint

Sample 1 Explanation

• 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.

Constraints

All input data satisfy the following conditions.

• $1 \leq N \leq 100\,000$.
• $1 \leq Q \leq 100\,000$.
• $1 \leq K \leq 10$.
• $0 \leq C_i \leq 1\,000\,000\,000$ ($1 \leq i \leq N$).
• $1 \leq S_i \leq 3$ ($1 \leq i \leq Q$).
• When $S_i = 1$ is satisfied, $1 \leq T_i \leq N$ and $0 \leq U_i \leq 1\,000\,000\,000$ ($1 \leq i \leq Q$).
• When $S_i = 2,3$ is satisfied, $1 \leq T_i \leq U_i \leq N$ ($1 \leq i \leq Q$).

Subtask

Subtask 1 [5 points]

• $1 \leq N \leq 3\,000$.
• $1 \leq Q \leq 3\,000$.

Subtask 2 [10 points]

• $K = 1$.

Subtask 3 [10 points]

• $C_i \leq 1$ ($1 \leq i \leq N$).
• When $S_i = 1$ is satisfied, $U_i \leq 1$ ($1 \leq i \leq Q$).

Subtask 4-10 [75 points]

There are no additional constraints.