Efficient Data Structure

Elly has two sequences $a\_1, a\_2, \ldots, a\_n$ and $b\_1, b\_2, \ldots, b\_n$. She would like to perform the following operations:

• 1 $x$ $y$, change the value of $a\_x$ to $y$.
• 2 $x$ $y$, change the value of $b\_x$ to $y$.
• 3 $x$, find the value of $c\_x$, where $c\_0=0$, $c\_i=\max(c\_{i-1}+b\_i,a\_i) \text{ for } 1 \le i \le x$.

Implement an efficient data structure to process those operations.

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains two integers $n$ and $m$ , which are the length of the two sequences and the number of operations. The second line contains $n$ integers $a\_1, a\_2, \ldots, a\_n$. The third line contains $n$ integers $b\_1, b\_2, \ldots, b\_n$. Each of the last $m$ lines contains a query.

For each query of type 3, output an integer denoting the value of $c\_x$.

• $1 \leq n, m \leq 2 \times 10^5$
• $-10^9 \leq a\_i, b\_i, y \leq 10^9$
• $1 \leq x \leq n$
• The sum of $n$ and the sum of $m$ do not exceed $2 \times 10^6$.