E. Mingle
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The next season of Squid Game is about to begin! The Frontman put you in charge of the third game of the season, Mingle.

Mingle is defined by an initial number of players $$$p$$$, the number of safe rooms $$$m$$$, and a sequence of $$$k$$$ positive integers $$$b_1, \ldots, b_k$$$.

The game consists of $$$k$$$ rounds. In the $$$i$$$-th round, the remaining players need to form teams of size exactly $$$b_i$$$, and each team must hide in one of the $$$m$$$ safe rooms. Each safe room admits at most one team. If a player doesn't join a team of size $$$b_i$$$, or their team doesn't hide in a safe room, they are eliminated.

All players who survive the $$$i$$$-th round advance to the next, $$$i+1$$$-th round. Teams may change arbitrarily between rounds. Players who have made it past round $$$k$$$ are declared the winners of Mingle.

The Frontman is interested in computing the maximum possible number of winners in the game. However, since neither the initial number of players nor the sequence itself has been determined yet, you need to answer multiple queries about the game.

At the start, you are given a sequence $$$a$$$ of size $$$n$$$ and the number of safe rooms $$$m$$$, fixed for all queries. Then, $$$q$$$ queries follow. Each query is one of two types:

  • $$$1 \; i \; x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^9$$$) — update $$$a_i := x$$$.
  • $$$2 \; l \; r \; p$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq p \leq 10^9$$$) — what is the maximum number of winners in Mingle played on the sequence $$$a_l, a_{l+1}, \ldots, a_r$$$ with $$$m$$$ safe rooms and $$$p$$$ initial players?

For each query of type $$$2$$$, output the maximum possible number of winners. Note that queries of type $$$2$$$ are independent from each other.

Input

The first line contains two integers $$$n, m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 100$$$) — the size of $$$a$$$, and the number of safe rooms.

The second line contains $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial sequence.

The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.

The next $$$q$$$ lines describe the queries, one per line, in the format specified above.

Output

Output the answers to the queries of type $$$2$$$, one per line, in the order that they appear in the input.

Examples
Input
5 50
10 4 3 6 2
5
2 1 5 255
1 3 13
2 1 4 456
1 5 7
2 3 5 150
Output
100
192
133
Input
6 30
18 55 19 30 87 10
6
2 2 4 540
1 4 41
2 1 6 350
1 1 49
2 1 5 666
2 3 6 210
Output
480
260
522
170
Input
3 100
40 50 60
4
2 1 3 4000
1 1 30
1 3 45
2 1 3 4000
Output
3960
2970
Note

In the first query of the first test case, no more than $$$100$$$ players can survive the $$$5$$$-th round due to the limited number of safe rooms.

In the third query of the first test case, no more than $$$200$$$ players can survive the $$$2$$$-nd round. Then, in the $$$3$$$-rd round, these $$$200$$$ players can form up to $$$15$$$ teams of size $$$13$$$, leaving $$$5$$$ players behind. In the $$$4$$$-th round, the remaining $$$195$$$ players can form up to $$$32$$$ teams of size $$$6$$$, resulting in $$$192$$$ winners.