C. Road Cycling
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Road cycling is one of the sports in which Kazakh athletes excel the most. Thus, to strengthen ties with Kazakhstan, the Brazilian Cycling Society (SBC) decided to organize a cycling marathon on Kazakh territory!

With the intention of attracting the largest number of competitors of all levels, the marathon organized by the SBC is different from the usual ones. The circuit has $$$n$$$ stations where cyclists can stop to rest, drink an energy drink for free, and continue. The stations are arranged in a circular manner. In other words, for $$$1 \leq i \lt n$$$, station $$$i + 1$$$ is immediately after station $$$i$$$, and station $$$1$$$ follows station $$$n$$$. The energy drink available at station $$$i$$$ gives the cyclist $$$b_i$$$ units of energy. The amount of energy required to go from station $$$i$$$ to the next is $$$c_i$$$ units. Thus, a cyclist with $$$x$$$ units of energy can move from station $$$i$$$ to the next only if $$$x \geq c_i$$$. Moreover, he loses $$$c_i$$$ units of energy when doing so.

The SBC is testing different scenarios to decide how to better organize the marathon. Your task is to help them answer 3 different types of queries:

  • $$$1$$$ $$$i$$$: Suppose a cyclist with initial energy 0 starts his journey at station $$$i$$$. Tell which is the last station he can reach before stopping. If the cyclist can continue indefinitely, print $$$-1$$$.
  • $$$2$$$ $$$i$$$ $$$x$$$: Assign the value $$$x$$$ to $$$b_i$$$.
  • $$$3$$$ $$$i$$$ $$$x$$$: Assign the value $$$x$$$ to $$$c_i$$$.
Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$), the number of stations and the number of queries, respectively.

The second line contains $$$n$$$ integers, the values of $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$).

The third line contains $$$n$$$ integers separated, the values of $$$c_i$$$ ($$$1 \leq c_i \leq 10^9$$$).

The following $$$q$$$ lines describe the queries in the format explained in the statement. It is guaranteed that the index $$$i$$$ is between $$$1$$$ and $$$n$$$ and that the assigned value $$$x$$$ is such that $$$1 \leq x \leq 10^9$$$.

Output

For each query of type 1, print the last station the cyclist can reach before stopping or $$$-1$$$ if he can continue indefinitely.

Example
Input
5 4
3 2 5 8 1
2 3 4 7 6
1 2
1 1
3 4 2
1 1
Output
2
5
-1