By the wind storm's blast
From Mimuro's mountain slopes
Maples leaves are torn,
Which turn Tatsuta River
Into a rich brocade.
—
Chihaya and Taichi are playing a game of Karuta. During one round, they heard the song related to the poem above, and they remembered the following problem. Please help them solve it so they can continue playing!
A category-$$$k$$$ storm is coming and will blow the leaves off of a nearby tree. During the storm, the wind speed will vary: at time $$$t$$$ seconds after the storm begins, the wind speed is $$$w_t = a_t + k \cdot d_t$$$ units per second, for some time-varying additive and multiplicative base speeds $$$a_t$$$ and $$$d_t$$$.
There are $$$n$$$ leaves attached to a tree. The $$$i$$$th leaf starts at position $$$(0, y_i)$$$ and detaches from the tree at time $$$\ell_i$$$. In between times $$$t$$$ and $$$t+1$$$, any leaf that detached from the tree at time $$$t$$$ or earlier and hasn't yet hit the ground (at $$$y=0$$$) travels 1 unit down and $$$w_t$$$ units to the right; i.e. a leaf at position $$$(x,y)$$$ moves to $$$(x+w_t, y-1)$$$. Leaves that hit the ground never move again.
After the storm, you will need to rake up all the leaves, and need to know the farthest distance along the $$$x$$$-axis that any leaf will hit the ground. You might learn more accurate information about the storm in the future, and will need to recompute this farthest distance if $$$k$$$, $$$a_t$$$, or $$$d_t$$$ change.
The first line of the input contains three space-separated integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \leq n, m \leq 10^4$$$, $$$1 \leq q \leq 10^5$$$): the number of leaves, maximum height of the tree, and the number of weather updates, respectively.
The next line contains $$$n + m - 1$$$ space-separated integers $$$a_t$$$ ($$$1 \leq a_t \leq 10^6$$$), the additive component of wind speed at each second $$$t$$$.
The next line contains $$$n + m - 1$$$ space-separated integers $$$d_t$$$ ($$$1 \leq d_t \leq 10^6$$$), the multiplicative component of wind speed at each second $$$t$$$.
Each of the next $$$n$$$ lines contains two space-separated integers $$$\ell_i$$$ and $$$y_i$$$ ($$$1 \leq \ell_i \leq n, 1 \leq y_i \leq m$$$) and specifies a leaf on the tree that begins at $$$(0,y_i)$$$ and detached from the tree at second $$$\ell_i$$$.
The next $$$q$$$ lines contain the weather updates. Each update takes one of the following three forms:
It is guaranteed that there is at least one update of the first type.
Print one line for each update to the storm category $$$k$$$. On each line, print one integer: the maximum horizontal distance a leaf hits the ground given the information in the weather updates so far.
3 5 6 1 1 1 1 2 3 4 8 1 1 1 1 1 1 1 3 2 1 3 5 1 0 1 2 2 3 1 3 3 2 1 1 1 2
11 23 17 25
