Một thử thách khó khăn dành cho các bạn thí sinh tham gia kỳ thi Olympic Miền Nam 2025 tại Tây Ninh là một trò chơi mô phỏng sắp xếp được Ban tổ chức chuẩn bị công phu.

Hệ thống trò chơi bao gồm ~N~ kho xếp liên tiếp nhau, được đánh số từ ~1~ đến ~N~. Hiện tại, kho thứ ~i~ đang có đúng một vật thể có giá trị nguyên ~A_i~, và các giá trị ~A_i~ này là đôi một khác nhau ~(1 \le i \le N)~. Bài toán giả định tại một thời điểm nào đó, mỗi kho có thể chứa một số lượng tùy ý các vật thể cùng một lúc.

Giữa một cặp kho liên tiếp ~i~ và ~i+1~ ~(1 \le i < N)~ có một chi phí di chuyển cố định ~C_i~. Để di chuyển một vật thể từ kho ~i~ sang kho ~i+1~ (hoặc ngược lại), thí sinh cần trả đúng chi phí ~C_i~ tương ứng.

Hệ thống yêu cầu thí sinh tính chi phí di chuyển phải trả nếu sắp xếp lại các vật thể bằng cách liên tục thực hiện các phép di chuyển đã mô tả ở trên, sao cho:

• Các vật thể từ kho ~1~ đến kho ~N~ tạo thành một dãy không giảm về giá trị.

• Mỗi kho chứa đúng một vật thể.

• Tổng chi phí di chuyển phải trả là nhỏ nhất có thể.

Trong quá trình chơi, thí sinh sẽ nhận được ~Q~ yêu cầu truy vấn từ hệ thống, mỗi truy vấn thuộc một trong hai dạng sau:

• Dạng thứ nhất: ~1\ x\ y~, có ý nghĩa là hoán đổi giá trị của hai vật thể đang nằm ở kho ~x~ và kho ~y~.

• Dạng thứ hai: ~2\ p\ v~, có ý nghĩa là cập nhật chi phí di chuyển giữa kho ~p~ và kho ~p+1~ thành ~v~.

Sau mỗi lần truy vấn, hệ thống yêu cầu thí sinh tính chi phí di chuyển phải trả nếu sắp xếp lại các vật thể hiện tại theo yêu cầu trên. Lưu ý rằng mỗi hành động từng truy vấn đều được giữ lại và ảnh hưởng đến các truy vấn tiếp theo.

Input

• Dòng đầu tiên chứa một số nguyên duy nhất ~N~ ~(2 \le N \le 2 \times 10^5)~ là số lượng kho.

• Dòng thứ hai chứa ~N~ số nguyên ~A_1,A_2,\dots,A_N~ ~(1 \le A_i \le 10^9)~ là giá trị ban đầu của các vật thể trong từng kho. Các phần tử trong dãy này đôi một khác nhau.

• Dòng thứ ba chứa ~N-1~ số nguyên ~C_1,C_2,\dots,C_{N-1}~ ~(1 \le C_i \le 10^5)~ là chi phí di chuyển giữa các cặp kho liên tiếp.

• Dòng thứ tư chứa một số nguyên ~Q~ ~(0 \le Q \le 2 \times 10^5)~ là số lượng yêu cầu truy vấn của hệ thống.

• Mỗi dòng trong số ~Q~ dòng tiếp theo mô tả một truy vấn, thuộc một trong hai dạng:

  • ~1\ x\ y~: Hoán đổi giá trị của hai vật thể ở kho ~x~ và kho ~y~ ~(1 \le x,y \le N,\ x \ne y)~.

  • ~2\ p\ v~: Cập nhật lại chi phí di chuyển giữa kho ~p~ và kho ~p+1~ thành ~v~ ~(1 \le p < N;\ 1 \le v \le 10^5)~.

Dữ liệu đảm bảo tất cả giá trị ~A_i~ là phân biệt.

Output

Gồm ~Q+1~ dòng theo định dạng sau:

• Dòng đầu tiên in ra kết quả chi phí sắp xếp kho ban đầu.

• Mỗi dòng trong số ~Q~ dòng tiếp theo in ra chi phí sắp xếp tìm được sau khi thực hiện từng truy vấn tương ứng.

Scoring

Sample Input 1

3
1 3 2
1 2
2
2 2 3
1 2 3

Sample Output 1

4
6
0

Notes

• Ban đầu, trạng thái trò chơi là ~[(1),(3),(2)]~, chuyển ~3~ từ kho ~2~ sang kho ~3~ tốn chi phí ~C_2=2~, lúc này trạng thái trò chơi là ~[(1),(),(2,3)]~, tiếp tục chuyển ~2~ từ kho ~3~ sang kho ~2~ tốn chi phí ~C_2=2~. Như vậy tổng chi phí là ~2+2=4~.

• Thực hiện truy vấn ~2\ 2\ 3~, ~C_2~ được cập nhật thành ~3~. Các thao tác sắp xếp vẫn như trên, lúc này tổng chi phí là ~3+3=6~.

• Thực hiện truy vấn ~1\ 2\ 3~, hoán đổi giá trị của ~A_2~ và ~A_3~, khi đó ~A=(1,2,3)~. Trạng thái này đã thỏa mãn điều kiện nên tổng chi phí là ~0~.