Cho một mảng \(A\) ban đầu rỗng. Người ta cần thực hiện lần lượt \(Q\) truy
vấn sau:

• \(1\) \(x\): Thêm giá trị nguyên \(x\) vào cuối mảng \((0 \le x \le 10^9)\).
• \(2\): In ra giá trị ở vị trí đầu tiên của mảng. Dữ liệu đảm bảo lúc này \(A\) có ít nhất một phần tử. Sau đó xoá phần tử này đi.
• \(3\): Sắp xếp lại mảng theo thứ tự không giảm.

Input

• Dòng đầu tiên nhập một số nguyên dương \(Q\) \((Q \le 2 \times 10^5)\) là số lượng truy vấn.

Output

• In ra đáp án với mỗi truy vấn thuộc loại \(2\).

Subtask

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): luôn có truy vấn loại \(3\) xuất hiện sau truy vấn loại \(1\).
• Subtask \(2\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

8
1 3
1 4
1 1
2
3
2
1 3
2

3
1
4

Cho một mảng \(A\) ban đầu rỗng. Người ta cần thực hiện lần lượt \(Q\) truy
vấn sau:

• \(1\) \(x\): Thêm giá trị nguyên \(x\) vào cuối mảng \((0 \le x \le 10^9)\).
• \(2\): In ra giá trị ở vị trí đầu tiên của mảng. Dữ liệu đảm bảo lúc này \(A\) có ít nhất một phần tử. Sau đó xoá phần tử này đi.
• \(3\): Sắp xếp lại mảng theo thứ tự không giảm.

Input

• Dòng đầu tiên nhập một số nguyên dương \(Q\) \((Q \le 2 \times 10^5)\) là số lượng truy vấn.

Output

• In ra đáp án với mỗi truy vấn thuộc loại \(2\).

Subtask

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): luôn có truy vấn loại \(3\) xuất hiện sau truy vấn loại \(1\).
• Subtask \(2\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

8
1 3
1 4
1 1
2
3
2
1 3
2

3
1
4

Cho dãy số nguyên \(a\) độ dài \(n\), bạn phải lần lượt thực hiện thao tác đúng \(2\) lần, mỗi thao tác bao gồm \(2\) bước sau:

• Chọn \(2\) giá trị \(l\), \(r\) sao cho \(1 \leq l \leq r \leq n\).
• Đổi dấu các phần tử trong đoạn từ \(l\) đến \(r\) của dãy \(a\). Nói cách khác, gán \(a[i] = -a[i]\) với mọi \(l \leq i \leq r\).

Hãy tìm cách thực hiện đúng \(2\) thao tác sao cho sau khi thực hiện, tổng các phần tử dãy \(a\) là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên \(n\) là độ dài của dãy \(a\) (\(n \leq 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, a_3,..., a_n\) là các phần tử của dãy \(a\) (\(-10^9 \leq a_i \leq 10^9\))

Output

• Một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 1000\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

4
-1 2 -3 -4

10

Bạn được cho một mảng \(a\) gồm \(n\) phần tử nguyên dương phân biệt. Ở mỗi bước, bạn có thể chọn ra một số nguyên dương \(x\), sao cho \(x\) không xuất hiện trong dãy \(a\), sau đó thêm số \(x\) vào đuôi của \(a\).

Để tránh biến đây thành một chuỗi hành động dài vô tận, bạn quyết định sẽ dừng lại khi tổng của các phần tử trong dãy \(a\) lớn hơn hoặc bằng giá trị \(k\) cho trước.

Bạn muốn chơi trò chơi này lâu nhất có thể (hơi ngược đời nhỉ), vậy nên hãy tìm ra chiến thuật tốt nhất để chơi được nhiều lượt nhất!

Input

• Dòng đầu chứa hai số nguyên dương \(n,k\) miêu tả độ dài của dãy \(a\) ban đầu và số \(k\) cho trước \((1 \le n \le 2 \times 10^5, 1 \le k \le 10^{18})\).
• Dòng thứ hai chứa \(n\) số nguyên dương phân biệt \(a_1,a_2,...,a_n\) \((1 \le a_i \le 10^{12})\).

Output

• Gồm một số nguyên dương là số lượt chơi lâu nhất có thể nếu bạn chơi tối ưu.

Subtask

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 100, k \le 10^6\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 1000, k \le 10^9\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^5, k \le 10^{12}\)
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm

Sample input 1

3 15
1 3 5

Sample output 1

2

Sample input 2

5 35
1 4 2 6 12

Sample output 2

3

Explanation:

• Ở ví dụ thứ nhất, bạn chỉ có thể chơi \(2\) lượt, giả sử bạn lần lượt thêm vào \(2\), dãy sau đó trở thành \([1,3,5,2]\), và ở lượt sau bạn thêm vào \(4\), dãy trở thành \([1,3,5,2,4]\). Lúc này dãy đã vừa đủ có tổng bằng \(k=15\) nên sẽ không được thêm nữa.

Châu đang tham gia một chương trình được tổ chức bởi người bạn của anh ấy, Huy. Chương trình mang tên: "Sing tồn tại NUS". Trong chương trình này, Châu phải băng qua một công viên hình chữ nhật kích thước \(3 × n\), gồm \(3\) hàng và \(n\) cột. Mỗi hàng có các ô được đánh số từ \(1\) đến \(n\), từ trái sang phải.

Mỗi ô trên công viên chứa một số nguyên \(a_{i,j}\). Ban đầu, điểm của Châu bằng \(0\), và mỗi khi Châu đến một ô ở hàng \(i\) và cột \(j\), điểm số của anh ấy sẽ cộng thêm \(a_{i,j}\). Lưu ý rằng điểm số có thể trở thành số âm.

Ban đầu, tất cả các ô ở hàng thứ nhất và hàng thứ ba được đánh dấu là có thể đi qua, trong khi tất cả các ô ở hàng thứ hai bị đánh dấu là không thể đi qua. Tuy nhiên, Huy đã đưa ra một số hỗ trợ cho Châu: có \(q\) ưu đãi đặc biệt trong chương trình, ưu đãi thứ \(i\) cho phép Châu đánh dấu các ô trong hàng thứ hai giữa các cột \(l_i\) và \(r_i\) là có thể đi qua. Tuy nhiên, mỗi khi Châu chấp nhận một ưu đãi đặc biệt, điểm số của anh ấy sẽ giảm đi \(k_i\). Châu có thể sử dụng bao nhiêu ưu đãi tùy ý, và có thể đánh dấu cùng một ô nhiều lần.

Châu bắt đầu hành trình của mình ở hàng thứ nhất và cột thứ nhất, và anh ấy muốn đến ô ở hàng thứ ba và cột cuối cùng. Anh ấy chỉ có thể di chuyển xuống hàng dưới hoặc sang phải cột tiếp theo (nghĩa là tăng chỉ số hàng hoặc cột lên \(1\)), như vậy tổng cộng Châu sẽ thực hiện \(n + 1\) bước, trong đó \(n - 1\) bước sẽ là di chuyển ngang và \(2\) bước sẽ là di chuyển dọc.

Huy hứa sẽ trả tiền cho Châu dựa trên điểm số cuối cùng của anh ấy, vì vậy điểm số cuối cùng sẽ là tổng tất cả các số của các ô Châu đã đi qua, trừ đi chi phí của tất cả các ưu đãi đặc biệt mà Châu đã sử dụng.

Tất nhiên, nếu điểm số âm thì Châu sẽ phải trả rất nhiều tiền, vậy nên hãy giúp Châu. tối đa hóa điểm số cuối cùng của mình.

Input

• Dòng đầu chứa hai số nguyên dương \(n,q\) mô tả số cột của công viên và số ưu đãi đặc biệt.
• Ba dòng sau, dòng thứ \(i\) gồm \(n\) số nguyên: \(a_{i,1}, a_{i,2}, ..., a_{i,n}\).
• \(q\) dòng sau, dòng thứ \(i\) gồm \(3\) số nguyên dương \(l_i,r_i,k_i\) \((1 \le l_i \le r_i \le n; 1 \le k_i \le 10^9)\) miêu tả khuyến mãi đặc biệt thứ \(i\).

Output

• Gồm một dòng in ra số tiền lớn nhất Châu có thể thu về.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(q = 1\)
• Subtask \(2\) (\(15\%\) số điểm): \(n,q \le 500\)
• Subtask \(3\) (\(15\%\) số điểm): \(n \le 2000, q \le 5000\)
• Subtask \(4\) (\(20\%\) số điểm): Tất cả \(k_i\) đều bằng nhau.
• Subtask \(5\) (\(20\%\) số điểm): \(n,q \le 10^5\)
• Subtask \(6\) (\(15\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 3
1 0 2 -2
-5 3 9 1
-1 2 4 1
2 3 4
1 4 15
1 2 6

13

5 4
-20 -100 -15 -8 4
1 3 4 6 7
14 -22 3 2 2
1 5 13
1 2 4
3 5 5
2 3 2

-6