Cho dãy ~A~ là dãy nhị phân, độ dài ~N~. Hãy xoá một số phần tử để dãy còn lại có độ dài ~k~. Và với mọi ~1 < i < k~ thì ~a_{i - 1} + a_{i + 1}~ = ~1~.

Input

• Một dòng duy nhất chứa một xâu nhị phân.

Output

• In ra dãy dài nhất thoả mãn. Nếu có nhiều kết quả, in ra tuỳ ý.

Subtask

• Gọi ~n~ là độ dài xâu nhị phân.

• ~30\%~ số test thỏa mãn ~1 \le n \le 20~.

• ~70\%~ số test còn lại có ~1 \le n \le 100~.

Sample Input 1

01010101

Sample Output 1

011001

Sample Input 2

001

Sample Output 2

001

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~.

Sample Input 1

7
1 2
1 1
2
3
2
1 3
2

Sample Output 1

2
1
3

Note

• Có ~50\%~ số test thoả mãn ~n \le 1000~.

• Các tests còn lại không có ràng buộc gì thêm.

Cho một dãy số nguyên ~A~ độ dài ~N~. Tìm ra ~K~ đoạn con liên tiếp không có phần tử chung, không rỗng sao cho tổng của tất cả phần tử được chọn là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~K, N~ ~(1 \leq N \leq 10^5, 1 \leq K \leq min(N, 100))~.

• Dòng tiếp theo gồm ~N~ số nguyên cách nhau bởi dấu cách ~A_1, A_2, \ldots, A_N~ ~(-10^9 \leq A_i \leq 10^9)~.

Output

• In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

Sample Input 1

7 3
1 -2 3 -4 5 -6 7

Sample Output 1

15

Sample Input 2

7 3
3 -2 3 -4 7 -6 7

Sample Output 2

18

Note

• Có ~\frac{18}{61}~ tests thoả mãn ~k = 2~.

• Có ~\frac{18}{61}~ tests thoả mãn ~k = 3~.

• Các tests còn lại không có ràng buộc gì thêm.

Cho một dãy số nguyên dương ~A~ có ~n~ phần tử. Hãy đếm số đoạn con liên tiếp, không rỗng và cân bằng của dãy. Được biết một đoạn ~[l, r]~ được coi là cân bằng nếu như ~O \ge E^2 + 7~ với ~O~ là số lượng số lẻ và ~E~ là số lượng số chẵn trong đoạn con đó.

Input

• Dòng đầu tiên chứa số ~n~, độ dài của dãy số ~(1 \le n \le 3 \times 10^5)~

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~

Output

• Một số nguyên dương duy nhất là số đoạn con ~[l, r]~ cân bằng.

Subtask

• ~20\%~ số test đầu có ~n \leq 1000~.

• ~30\%~ số test khác thoả mãn ~n \le 10^5~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

11
1 2 1 1 1 1 1 1 1 1 2

Sample Output 1

7

Note

• Có ~7~ đoạn con cân bằng đó là ~[1, 9], [1, 10], [2, 10], [3, 9], [3, 10], [3, 11], [4, 10]~

Cho một tập tập ~S~ với kích thước ~m~ và một số nguyên dương ~n~; mỗi phần tử của tập hợp là một cặp số ~(x,y)~ thỏa mãn:

• ~1\le x \le n~

• ~1\le y \le n~

• ~x\neq y~

Đồng thời; với hai phần tử ~(x, y)~ và ~(u,v)~ bất kì thuộc ~S~ thì:

• ~u\neq x~ hoặc ~v \neq y~

• ~v \neq x~

Yêu cầu: Hãy tìm tập ~P~ có tính chất tương tự tập ~S~ thỏa mãn ~P \cap S = \emptyset ~ và ~P~ có kích thước càng lớn càng tốt

Input

• Dòng đầu tiên chứa hai số nguyên dương ~m,n~ (~m\le 10^6, n\le 2\times 10^3~)

• ~m~ dòng tiếp, mỗi dòng gồm hai số nguyên mô tả một phần tử của tập ~S~

Output

• In ra một số nguyên là số phần tử của tập ~P~ bạn tìm được

• ~|P|~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên mô tả một phần tử của tập ~P~

Subtask

Gọi ~GK~ là lực lượng tập ~P~ trong đáp án của Ban giám khảo, và ~TS~ là lực lượng tập ~P~ trong đáp án của bạn. Với mỗi test bạn sẽ được:

• Toàn bộ số điểm nếu ~TS \ge GK~

• ~- 0.416 \times \log_{10}(\frac{GK-TS}{GK})~ Nếu ~TS < GK~

Sample Input 1

1 3
1 2

Sample Output 1

2
1 3
2 3

Note

Dễ thấy tập trên là tập có kích thước lớn nhất thỏa mãn điều kiện