Description

有一天你走在路上被閃電打到,醒來之後發現自己竟然穿越到了異世界,還變成了一隻牛。
你身處於農夫約翰的農場,這時的你還不知道這座農場將因你颳起一陣腥風血雨,第五次牛丼戰爭、第七次菲力危機……,而那又是另外一段故事了。

農夫約翰養了 $n$ 隻牛,這些牛會按照編號排成一直線的隊伍,由左到右的編號為 $1\sim n$。
每隻牛都有身高與體重,編號 $i$ 的牛身高為 $h_i$,體重為 $w_i$。

每隻牛可以往左看或往右看,編號 $i$ 的牛可以看到編號 $j$ 的牛的條件是:

  • $h_j\leq h_i$
  • 不存在一個 $k$ 滿足 $\min(i,j)<k<\max(i,j)$ 且 $h_k\ \textgreater\ h_i$,也就是說只要中間沒有比較高的牛擋住,那編號 $i$ 的牛可以看到身高不高於自己的牛。
  • 根據定義,一隻牛是可以看到自己的。

接下來會有 $q$ 個操作,每種操作會有兩種可能:

  • 操作為 $1\ p\ x$:將 $w_p$ 設為 $x$。
  • 操作為 $2\ p$:詢問編號 $p$ 的牛能看到的牛的體重總和。

Input Format

第一行有兩個正整數 $n,q$,代表農夫約翰有幾隻牛和操作數量。
第二行有 $n$ 個正整數 $h_1\sim h_n$,代表每隻牛的身高。
第三行有 $n$ 個正整數 $w_1\sim w_n$,代表每隻牛的體重。
接下來 $q$ 行,每行會有若干個正整數,可能為 $1\ p\ x$ 或 $2\ p$。

對於所有測試資料:

  • $1\leq n,q\leq 2\times 10^ 5$
  • $1\leq h_i,w_i\leq 10^ 9$
  • $1\leq p\leq n$
  • $1\leq x\leq 10^ 9$

Output Format

對於每個 $2\ p$ 的操作,回答編號 $p$ 的牛能看到的牛的體重總和。

Sample Input 1

5 7
3 2 2 5 6
1 2 4 8 16
2 3
2 1
2 5
1 2 100
2 2
2 4
2 5

Sample Output 1

6
7
31
104
113
129

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~5 $n,q\leq 3000$ 18
3 1, 6~10, 21~25 只會有 $2\ p$ 的操作 19
4 1, 11~15 $h_i<h_{i+1}$($1\leq i<n$) 26
5 0~30 無其他限制 37

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 5
1 1000 65536 65536 2 3 4 5
2 1000 65536 65536 2 5
3 1000 65536 65536 2 5
4 1000 65536 65536 2 5
5 1000 65536 65536 2 5
6 1000 65536 65536 3 5
7 1000 65536 65536 3 5
8 1000 65536 65536 3 5
9 1000 65536 65536 3 5
10 1000 65536 65536 3 5
11 1000 65536 65536 4 5
12 1000 65536 65536 4 5
13 1000 65536 65536 4 5
14 1000 65536 65536 4 5
15 1000 65536 65536 4 5
16 1000 65536 65536 5
17 1000 65536 65536 5
18 1000 65536 65536 5
19 1000 65536 65536 5
20 1000 65536 65536 5
21 1000 65536 65536 3 5
22 1000 65536 65536 3 5
23 1000 65536 65536 3 5
24 1000 65536 65536 3 5
25 1000 65536 65536 3 5
26 1000 65536 65536 5
27 1000 65536 65536 5
28 1000 65536 65536 5
29 1000 65536 65536 5
30 1000 65536 65536 5