효율적인 자료 구조

Elly에게 길이가 $n$인 두 수열 $a\_1, a\_2, \ldots, a\_n$과 $b\_1, b\_2, \ldots, b\_n$이 있다. 다음 세 가지 연산을 처리하는 자료 구조를 구현하시오.

• 1 $x$ $y$: $a\_x$의 값을 $y$로 바꾼다.
• 2 $x$ $y$: $b\_x$의 값을 $y$로 바꾼다.
• 3 $x$: $c\_x$의 값을 구한다. 여기서 $c\_0=0$이고, $1 \le i \le x$인 모든 $i$에 대해 $c\_i=\max(c\_{i-1}+b\_i,a\_i)$이다.

입력은 여러 테스트 케이스로 이루어지며, 파일의 끝(EOF)에서 끝난다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$이 주어진다. 각각 수열의 길이와 연산의 개수이다. 둘째 줄에는 $n$개의 정수 $a\_1, \ldots, a\_n$이, 셋째 줄에는 $n$개의 정수 $b\_1, \ldots, b\_n$이 주어진다. 마지막 $m$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

타입 3 쿼리마다 $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$
• 모든 테스트 케이스에 걸친 $n$의 합과 $m$의 합은 각각 $2 \times 10^6$을 넘지 않는다.