Gấu từ nhỏ đã có ước mơ làm ca sĩ và ước mơ ấy đã thành hiện thực, nhưng cuộc đời thì không phải màu hồng, trong khi làm một ca sĩ nổi tiếng thì anh đã vấp một bê bối tình duyên khiến sự nghiệp sụp đổ. 5 năm sau, anh đã trở lại với một buổi họp báo quy mô lớn. Buổi họp báo này quy tụ rất đông đảo các người hâm mộ của anh trên khắp cả nước, cụ thể là ban đầu có ~n~ người tham gia họp báo. Sau cuộc họp, họ dự định sẽ xếp thành một hàng và xin chữ ký và chụp ảnh với Gấu, tuy nhiên không phải ai cũng rảnh rỗi.

Với người ~i~, họ chỉ rảnh trong thời gian từ ~1~ đến ~t_i~, do đó sau thời gian này, cứ mỗi ~1~ đơn vị thời gian, người hâm mộ thứ ~i~ sẽ mất ~1~ đơn vị tình yêu với Gấu. Ngược lại, nếu trong khoảng thời gian này, mỗi ~1~ đơn vị thời gian mà Gấu hoàn thành ký và chụp sớm sẽ khiến người ~i~ tăng thêm ~1~ đơn vị tình yêu với Gấu. Việc ký và chụp với người thứ ~i~ sẽ tốn thời gian là ~d_i~.

Tổng độ yêu thích sau cùng là tổng đơn vị tình yêu của tất cả người hâm mộ trong hàng dành cho Gấu sau khi hoàn thành ký và chụp cho tất cả người trong hàng. Do đó Gấu muốn chọn ra một thứ tự nào đó để thực hiện việc chụp và ký sao cho tổng độ yêu thích là lớn nhất.

Vì sự quay trở lại sau 5 năm này, trong thời gian ký và chụp đã có ~q~ sự kiện xảy ra:

• ~1~ ~p~ ~x~ ~y~: Vì quá thích Gấu, do đó có thêm một người với thời gian rảnh là ~x~ và thời gian để ký và chụp là ~y~ chen vào giữa người ~p~ và người ~p+1~. Nếu ~p = n~ thì người đó sẽ vào cuối hàng. Sau hành động này, số người trong hàng sẽ tăng lên ~1~ (hay ~n = n + 1~).
• ~2~ ~k~ ~x_1, x_2, \dots, x_k~: Gấu lo sợ rằng do mình ký và chụp hơi lâu, nên đã có ~k~ người ở các vị trí ~x_1, x_2, \dots, x_k~ bỏ về. Hãy tính tổng độ yêu thích còn lại.
• ~3~ ~D~: Tập những người ~i~ có ~d_i = D~ là một nhóm bạn (vì ký và chụp cùng lúc nên thời gian như nhau). Gấu lo sợ rằng do mình ký và chụp hơi lâu nên nhóm bạn này sẽ bỏ về. Hãy tính độ yêu thích còn lại.

Lưu ý rằng các sự bỏ về ở sự kiện loại ~2~ và ~3~ chỉ là sự lo sợ của Gấu, thực tế các người hâm mộ rất yêu thích Gấu nên không có ai bỏ về.

Dữ liệu vào

Đọc từ tệp văn bản fandom.inp

• Dòng đầu tiên chứa số nguyên ~\theta~ ~(1 \leq \theta \leq 4)~ là số thứ tự của subtask này.
• Dòng hai chứa hai số nguyên dương ~n, q~ ~(1 \leq n, q \leq 2*10^5)~.
• Dòng ba gồm ~n~ số nguyên mô tả dãy ~t~ ~(1 \leq t_i \leq 10^8)~.
• Dòng bốn gồm ~n~ số nguyên mô tả dãy ~d~ ~(1 \leq d_i \leq 10^8)~.
• ~q~ dòng sau, mỗi dòng chứa các sự kiện thuộc một trong ba loại:
  • ~1~ ~p~ ~x~ ~y~ ~(1 \leq p \leq n, 1 \leq x, y \leq 10^8)~.
  • ~2~ ~k~ ~x_1, x_2, \dots, x_k~ ~(1 \leq x_i \leq n)~.
  • ~3~ ~D~ ~(1 \leq D \leq 10^8)~.

Dữ liệu đảm bảo tổng ~k~ trong tất cả sự kiện loại ~2~ không vượt quá ~2*10^5~ và tổng sự kiện loại ~1~ không vượt quá ~10^5~ .

Dữ liệu ra

Ghi ra tệp văn bản fandom.out

Với mỗi sự kiện loại ~2~ và ~3~, hãy tính độ yêu thích còn lại nếu giả sử những người đó đã rời khỏi hàng. Các đáp án in trên cùng một dòng.

Ví dụ

Đầu vào

1
6 7
2 10 16 16 4 20
2 7 1 9 1 8
2 1 2
3 1
1 1 4 6
2 3 2 4 7
2 0
1 7 9 9
3 9

Đầu ra

18 -6 -1 -21 -3

Giải thích

Ở sự kiện ~1~, những người còn lại là ~(1, 3, 4, 5, 6)~, Gấu thực hiện theo thứ tự ~(3, 5, 1, 6, 4)~, khi đó:

• Người ~3~ được chụp ảnh vào thời điểm ~1~, Gấu nhận được ~16 - 1 = 15~ đơn vị tình yêu.
• Người ~5~ được chụp ảnh vào thời điểm ~2~, Gấu nhận được ~4 - 2 = 2~ đơn vị tình yêu.
• Người ~1~ được chụp ảnh vào thời điểm ~4~, Gấu nhận được ~2 - 4 = -2~ đơn vị tình yêu.
• Người ~6~ được chụp ảnh vào thời điểm ~12~, Gấu nhận được ~20 - 12 = 8~ đơn vị tình yêu.
• Người ~4~ được chụp ảnh vào thời điểm ~21~, Gấu nhận được ~16 - 21 = -5~ đơn vị tình yêu.
• Tổng đơn vị tình yêu bằng ~15 + 2 - 2 + 8 - 5 = 18~.

Ở sự kiện ~2~, những người còn lại là ~(1, 2, 4, 6)~. Thứ tự Gấu thực hiện là ~(1, 2, 6, 4)~.

Tính điểm

• Subtask 1 ($20\%$ số điểm): $1 \leq n, q \leq 1000$.
• Subtask 2 ($30\%$ số điểm): Không có sự kiện loại $1$ và $3$.
• Subtask 3 ($20\%$ số điểm): Không có sự kiện loại $1$.
• Subtask 4 ($30\%$ số điểm): Không có ràng buộc gì thêm.