407574: GYM102832 B The Tortoise and the Hare

Once there was a hare, who was addicted to sleeping. The hare lived in a town, where there were also $$$n$$$ tortoises living in a row on a street, numbered from $$$1$$$ to $$$n$$$.

The hare could run much faster than the tortoises, so he often challenged the tortoises $$$m$$$-meter run. During such a race, when the hare was just before the finish line, the $$$i$$$-th tortoises could only run $$$a_i$$$ meters.

On a race day, the hare would pick an interval, maybe $$$[l, r]$$$. The tortoises numbered between $$$l$$$ and $$$r$$$ (inclusive), together with the hare, would compete in an $$$m$$$-meter race. Just before the the finish line, the hare would sleep for a while, as he led the race so much.

The hare had trained an ability during his long-term sleepiness, which was to curse $$$k$$$ tortoises every second when sleeping. The ability was available as soon as he fell asleep. Any cursed tortoise would be trapped in place for a second when cursed. One tortoise might be cursed multiple times. As the hare had no ability to think during sleep, he simply chose the $$$k$$$ tortoises closest to the finish line when applying his cursing ability.

After the hare fell asleep, due to the anger caused by the leader sleeping and the companion being trapped, all tortoises not trapped began to run as fast as $$$1$$$ meter per second.

In order to win the game, if the hare could not trap all the tortoises that were only one meter away from the finish line at some moment, he must wake up and cross the finish line immediately.

The hare wondered how many seconds he could sleep during each race, and asked you for help.

However, the problem was not that easy. On every day when there was no race, the $$$m$$$-meter running speed of one of the turtles will increase due to diligent exercise (or maybe decrease due to lack of exercise). Specifically, after that day, the tortoise numbered $$$u$$$ could run $$$v$$$ meters before the hare was just before the finish line. Note that his running speed might be changed again in the future.

Now can you still tell the hare exactly how many seconds he could sleep in each race?

The first line contains three integers $$$n$$$, $$$m$$$ and $$$d$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$, $$$1 \leq d \leq 10^5$$$), where $$$d$$$ represents the number of days to be concerned.

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i < m$$$), representing the initial running speed of the tortoises.

Each of the next $$$d$$$ lines starts with an integer $$$r$$$ ($$$1 \leq r \leq 2$$$), describing one day.

• $$$r = 1$$$ indicates a racing day. Three integers $$$l$$$, $$$r$$$ and $$$k$$$ ($$$1 \leq l < r \leq n$$$, $$$1 \leq k \leq r - l$$$) follow on the same line.
• $$$r = 2$$$ indicates a day without racing. Two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u \leq n$$$, $$$1 \leq v < m$$$) follow on the same line.

For each racing day, print on a line the maximum seconds the hare could sleep in the race.

5 10 6
6 1 4 2 3
1 1 5 3
1 3 5 1
2 2 9
1 1 5 2
1 1 5 4
1 3 5 1

14
9
7
21
9

On the fourth day in the example, when the hare fell asleep, the tortoises each had completed $$$6$$$, $$$9$$$, $$$4$$$, $$$2$$$ and $$$3$$$ meters. The tortoises numbered $$$1$$$ and $$$2$$$ would be cursed, so one second later, the tortoises would have completed $$$6$$$, $$$9$$$, $$$5$$$, $$$3$$$ and $$$4$$$ meters. Repeating this procedure, one may find that all tortoises would have completed $$$9$$$ meters after $$$7$$$ seconds, just one meter before the finish line. As $$$5 > 2 = k$$$, the hare had to immediately wake up and run across the finish line.