Bài tập

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

Cho dãy gồm \(n\) số nguyên. Hãy đếm xem trong dãy có bao nhiêu số dương và bao nhiêu số âm (số \(0\) không thuộc loại nào).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên, cách nhau bởi dấu cách.

Output

Gồm hai dòng, đúng theo định dạng sau:

• Dòng thứ nhất: SO DUONG: theo sau là số lượng số dương.
• Dòng thứ hai: SO AM: theo sau là số lượng số âm.

Constraints

• \(1 \le n \le 1000\)
• \(|a_i| \le 10^9\)

Sample Input 1

6
4 0 -7 9 -1 -1

Sample Output 1

SO DUONG: 2
SO AM: 3