Bài tập

Tại hội đêm rằm, Nam có \(X\) điểm thưởng để đổi quà. Có \(N\) món quà, món thứ \(i\) có giá \(A_i\) điểm. Nam muốn đổi đúng hai món quà khác nhau (hai món ở hai vị trí khác nhau trong danh sách) sao cho tổng giá trị lớn nhất có thể nhưng không vượt quá \(X\).

In ra tổng giá trị đó. Nếu không có cặp nào có tổng không quá \(X\) (kể cả khi \(N = 1\)) thì in ra \(0\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(X\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

Một số nguyên là tổng giá trị lớn nhất không vượt quá \(X\) của hai món quà khác nhau, hoặc \(0\) nếu không thể.

Constraints

• \(1 \le N \le 100001\)
• \(1 \le X \le 10^9\)
• \(1 \le A_i \le 10^9\)

Sample Input

7 18
6 11 3 9 14 5 2

Sample Output

17

Explanation

Các cặp tốt nhất là \(14 + 3 = 17\) hoặc \(11 + 6 = 17\); không có cặp nào có tổng bằng \(18\).

Sudoku là trò chơi điền số trên lưới \(9 \times 9\) chia thành chín khối con \(3 \times 3\). Một lưới được điền đầy đủ khi mỗi hàng, mỗi cột và mỗi khối con \(3 \times 3\) đều chứa mỗi chữ số từ \(1\) đến \(9\) đúng một lần.

Cho một lưới Sudoku đã điền sẵn một số ô (các ô còn trống được ghi bằng số \(0\)). Hãy điền nốt các ô trống để hoàn thiện lưới. Dữ liệu đảm bảo lưới ban đầu chỉ có đúng một cách hoàn thiện.

Input

Gồm \(9\) dòng, mỗi dòng gồm \(9\) số nguyên từ \(0\) đến \(9\) cách nhau một dấu cách; số \(0\) nghĩa là ô trống.

Output

In ra lưới đã hoàn thiện gồm \(9\) dòng, mỗi dòng \(9\) số cách nhau một dấu cách.

Constraints

• Mỗi số trong lưới thuộc đoạn \([0, 9]\); các số khác \(0\) không vi phạm luật Sudoku.
• Lưới có đúng một nghiệm.

Sample Input

0 0 0 0 0 0 0 0 4
1 0 6 0 4 9 3 8 0
0 4 0 5 3 8 1 9 0
0 7 0 0 0 2 5 0 0
0 2 0 0 5 3 0 6 1
0 0 5 8 0 6 0 0 2
7 3 0 9 0 4 6 2 0
5 6 0 0 2 7 0 1 0
4 0 0 0 6 0 8 7 3

Sample Output

9 8 3 6 7 1 2 5 4
1 5 6 2 4 9 3 8 7
2 4 7 5 3 8 1 9 6
6 7 9 4 1 2 5 3 8
8 2 4 7 5 3 9 6 1
3 1 5 8 9 6 7 4 2
7 3 1 9 8 4 6 2 5
5 6 8 3 2 7 4 1 9
4 9 2 1 6 5 8 7 3

Trên mặt phẳng có \(N\) điểm được liệt kê theo một thứ tự cố định, điểm thứ \(i\) có toạ độ nguyên \((a_i, b_i)\). Ta muốn chọn ra một số điểm, giữ nguyên thứ tự xuất hiện của chúng, sao cho khi đi từ điểm chọn này sang điểm chọn kế tiếp thì cả hoành độ lẫn tung độ đều không giảm.

Nói cách khác, cần tìm dãy chỉ số \(i_1 < i_2 < \dots < i_k\) sao cho với mọi \(t\) ta có \(a_{i_t} \le a_{i_{t+1}}\) và \(b_{i_t} \le b_{i_{t+1}}\). Hãy tìm giá trị \(k\) lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\).

Output

In ra một số nguyên duy nhất là độ dài lớn nhất \(k\) của dãy điểm chọn được.

Constraints

• \(1 \le N \le 10^5\)
• \(0 \le a_i, b_i \le 10^3\)

Sample Input

7
4 4
2 6
5 4
5 7
1 9
8 8
5 7

Sample Output

4

Explanation

Chọn các điểm thứ 1, 3, 4, 6: \((4,4) \to (5,4) \to (5,7) \to (8,8)\). Không tồn tại dãy dài hơn.

Trong cách gọi của người Việt, thứ Hai là ngày đầu tuần, ..., thứ Bảy là ngày thứ sáu và Chủ nhật được gán số \(8\). Cho một số nguyên \(x\) từ \(2\) đến \(8\) tương ứng với một ngày trong tuần, hãy in ra tên tiếng Anh của ngày đó.

Ứng với \(x = 2, 3, \dots, 8\) lần lượt là: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.

Input

Một số nguyên \(x\) (\(2 \le x \le 8\)).

Output

Tên tiếng Anh của ngày tương ứng (chữ cái đầu viết hoa, các chữ còn lại viết thường).

Sample Input

5

Sample Output

Thursday