시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

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$.

예제 입력 1

4 9
1 2 3 3
-1 2 3 3
3 1
3 2
3 3
3 4
2 2 -4
3 1
3 2
3 3
3 4

예제 출력 1

1
3
6
9
1
2
5
8