Tăng chưa bao giờ nghĩ rằng, việc nhớ một người mới quen lại có thể khiến tim mình hỗn độn đến thế. Mọi thứ đến nhanh - tin nhắn đầu tiên, nụ cười vụng về, những lần gặp gỡ lúng túng, và cả ánh mắt khiến cậu chẳng thể rời đi.

Rồi một buổi chiều yên tĩnh ở Trường đại học quốc tế Miền Đông, trước kỳ thi Olympic Tin học sinh viên 2025, khi ngồi giữa những trang giấy trắng và dãy số dài, Tăng chợt nhận ra... ký ức về cô ấy cũng giống như những con số. Chúng rối tung và chưa theo trật tự nào, nhưng nếu cậu có thể sắp xếp chúng một cách đúng đắn - có lẽ mọi thứ sẽ trở nên dễ chịu hơn, như cách ta xếp lại những ngăn tủ trong lòng mình.

Cậu tưởng tượng ra một hệ thống kho ký ức - nơi mỗi kỷ niệm được đặt trong một chiếc hộp nhỏ, đánh số từ ~1~ đến ~N~. Mỗi hộp chứa đúng một "vật thể" mang giá trị cảm xúc của nó - có thể là nụ cười đầu tiên ~A_1~, tin nhắn tối hôm qua ~A_2~, hay khoảnh khắc em khẽ quay lại nhìn ~A_3,...~ . Tất cả các giá trị đó đều độc nhất, không có ký ức nào trùng với ký ức nào.

Tăng được biết rằng, giữa mỗi cặp kho liền kề ~i~ và ~i + 1~, tồn tại một chi phí ~C_i~ - đó là cái giá mà Tăng phải trả nếu muốn chuyển ký ức từ vị trí này sang vị trí kia, như thể mỗi lần muốn sắp xếp lại lòng mình, cậu đều phải đánh đổi chút bình yên.

Tăng được giao một nhiệm vụ - cũng là một phép thử của cảm xúc:

• Sắp xếp lại tất cả ký ức ấy sao cho chúng được đặt thành một dãy không giảm về giá trị, tức là những điều nhỏ bé, dịu dàng sẽ dần dần dẫn đến những điều lớn lao, sâu sắc hơn.
• Khi sắp xếp xong, mỗi kho phải chứa đúng một vật thể, không được bỏ sót, không được chồng chéo.
• Và điều mà Tăng mong muốn nhất là tổng chi phí cảm xúc - tức tổng chi phí di chuyển khi sắp xếp các vật thể phải nhỏ nhất có thể.

Nhưng mọi thứ không đứng yên mãi. Giống như cảm xúc của con người, hệ thống ký ức ấy cũng thay đổi theo thời gian. Trong suốt quá trình "chơi", hay có lẽ là trong quá trình "nhớ", Tăng sẽ nhận được ~Q~ truy vấn - như những sự kiện nhỏ diễn ra trong mối quan hệ:

• Có khi, hai kho ký ức bị hoán đổi – như khi ta bất chợt thấy thứ từng mờ nhạt trở nên rõ ràng hơn.
• Có khi, chi phí để di chuyển giữa hai kho thay đổi – như khi khoảng cách giữa hai trái tim trở nên xa hơn hay gần lại.

Sau mỗi thay đổi ấy, Tăng lại phải tính toán lại tổng chi phí cảm xúc ít nhất nếu muốn sắp xếp lại mọi thứ cho ổn thỏa. Cứ thế, mỗi truy vấn là một nhịp tim khác nhau, mỗi lần sắp xếp lại là một lần Tăng học cách đối diện với chính mình.

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)~ - số lượng kho ký ức.
• Dòng thứ hai: chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~` ~(1 \le A_i \le 10^9)~, là giá trị cảm xúc ban đầu trong từng kho. Các giá trị này đôi một khác nhau.
• Dòng thứ ba: chứa ~N - 1~ số nguyên ~C_1, C_2,..., C_{N-1}~ ~(1 \le C_i \le 10^5)~, là chi phí cảm xúc khi chuyển giữa hai kho ký ức liên tiếp.
• Dòng thứ tư: chứa một số nguyên ~Q~ ~(0 ≤ Q ≤ 2 \times 10^5)~ - số lượng thay đổi mà hệ thống sẽ gửi đến.
• Tiếp theo là ~Q~ dòng, mỗi dòng mô tả một truy vấn:
  • ~1~ ~x~ ~y~: Hoán đổi giá trị của hai vật thể ở kho ~x~ và ~y~ ~(1 \le x, y \le N, x ≠ 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)~.

Output

• Gồm ~Q + 1~ dòng:
  • Dòng đầu tiên in ra tổng chi phí sắp xếp trong trạng thái ban đầu (trước khi có truy vấn).
  • Mỗi dòng tiếp theo in ra tổng chi phí sắp xếp tối thiểu sau khi thực hiện từng truy vấn tương ứng.

Sample Input

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

Sample Output

4
6
0

Giải thích

• Ban đầu, các kho ký ức có thứ tự là ~(1, 3, 2)~ - mọi thứ chưa sẵn sàng, còn rối rắm. Để sắp xếp lại sao cho mạch cảm xúc dần tăng ~(1, 2, 3)~, Tăng cần di chuyển ký ức ~3~ qua một đoạn chi phí ~2~, rồi lại đưa ~2~ trở lại chỗ cũ - tổng chi phí là ~4~.
• Khi khoảng cách giữa hai kho thay đổi (chi phí ~C_2~ tăng lên thành ~3~), việc nhớ lại trở nên khó hơn - chi phí cảm xúc tăng lên thành ~6~.
• Cuối cùng, khi Tăng hoán đổi vị trí hai ký ức (như thể trong lòng cậu mọi thứ đã tự nhiên trở về đúng vị trí của nó), dãy trở nên hoàn hảo - ~(1, 2, 3)~. Và lúc ấy, tổng chi phí cảm xúc là ~0~. Một trạng thái yên bình hiếm hoi - như thể sau bao nhiêu rối ren, trái tim cuối cùng cũng biết sắp xếp lại chính mình.

Ràng buộc

• Subtask ~1~ ~(25\%)~: ~N, Q \le 200~.
• Subtask ~2~ ~(20\%)~: ~N, Q \le 5000~, chỉ có truy vấn loại ~2~.
• Subtask ~3~ ~(20\%)~: ~N, Q \le 5000~.
• Subtask ~4~ ~(20\%)~: chỉ có truy vấn loại ~2~.
• Subtask ~5~ ~(15\%)~: không có ràng buộc gì thêm.