問題文

数直線上に $N$ 匹のスライムが一列に並んでおり、$1$ から $N$ の番号がつけられています。

番号 $i$ のスライムは座標 $i$ におり、レベルは $A_i$ で、倒すと $X_i$ だけレベルが上がり、スライムは消滅します。 ここで、スライムのレベル $A_i$ は全て異なります。

初めの時点であなたは座標 $k + 0.5$ におり、レベルは $L$ です。

• 現在の座標を $x$ としたときに、座標 $x - 1$ に移動する。この操作は、座標 $x - 1$ と $x$ の間にスライムがいない場合にのみ行える。
• 現在の座標を $x$ としたときに、座標 $x + 1$ に移動する。この操作は、座標 $x$ と $x + 1$ の間にスライムがいない場合にのみ行える。
• 現在の座標を $x$ としたときに、座標 $x - 0.5$ にスライムがいた場合に倒す。この操作は、そのスライムのレベルがあなたのレベルより真に低い場合にのみ行える。
• 現在の座標を $x$ としたときに、座標 $x + 0.5$ にスライムがいた場合に倒す。この操作は、そのスライムのレベルがあなたのレベルより真に低い場合にのみ行える。

$Q$ 個のクエリが与えられるので、順番に処理してください。

クエリは次の $2$ 種類のいずれかです。

• 1 a b: 番号 $a$ のスライムを倒した際に上がるレベルを $b$ に変更する。つまり、$X_a = b$ に変更する。
• 2 c: $k = c$ の場合について、あなたが達成できるレベルの最大値を出力する。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L \leq 10^{15}$
• $1 \leq A_i \leq 10^{15}$
• $1 \leq X_i \leq 10^9$
• $1 \leq a \leq N$
• $1 \leq b \leq 10^9$
• $1 \leq c \leq N - 1$
• $A_i$ は全て異なる。
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $L$ 
$A_1$ $A_2$ ... $A_{N}$ 
$X_1$ $X_2$ ... $X_{N}$
query $1$  
query $2$  
$\vdots$

query $Q$ 

各クエリは以下に示す $2$ つの形式のいずれかが与えられる。

$1$ $a$ $b$ 

$2$ $c$

出力

$2$ のクエリの個数を $q$ として、$q$ 行出力せよ。

$j$ $(1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

サンプル

5 6 50
30 55 20 65 40
10 5 5 20 10
2 1
2 2
2 3
2 4
1 3 10
2 3

100
55
55
60
105

4 9 47
69 60 3 46
7 1 8 3
2 1
2 3
2 2
1 3 1
1 1 15
2 2
1 1 13
2 1
1 1 3

47
58
58
51
47