Bài tập

Trên bàn cờ vua kích thước \(n \times n\) có ba quân: một quân Vua của Sắn và hai quân Hậu của Dũng. Hai quân Hậu đứng yên tại chỗ suốt ván đấu, chỉ có Vua di chuyển.

Một ô bị Hậu khống chế nếu nó nằm cùng hàng, cùng cột hoặc cùng đường chéo với một trong hai quân Hậu (kể cả ô mà quân Hậu đang đứng). Vua mỗi lượt được đi sang một ô kề (ngang, dọc hoặc chéo, tức tối đa 8 hướng) nằm trong bàn cờ, với điều kiện ô đó không bị Hậu khống chế. Vua không được phép bước vào ô đang có Hậu, và có thể đi số lượt không giới hạn. Khi tính vùng bị khống chế, ta bỏ qua việc quân Vua có thể che chắn đường đi của Hậu.

Cho vị trí ban đầu của Vua và một ô đích \((x, y)\). Hãy cho biết Vua có thể đi tới ô đích hay không. Nếu ô đích trùng với ô xuất phát thì đáp án là YES.

Input

• Dòng 1: số nguyên \(n\), kích thước bàn cờ.
• Dòng 2: bốn số nguyên \(u_1, v_1, u_2, v_2\) - toạ độ (hàng, cột) của hai quân Hậu (hai vị trí khác nhau).
• Dòng 3: hai số nguyên \(s_x, s_y\) - vị trí ban đầu của Vua (đảm bảo không bị Hậu khống chế).
• Dòng 4: hai số nguyên \(x, y\) - ô đích.

Output

In YES nếu Vua đến được ô đích, ngược lại in NO.

Constraints

• \(3 \le n \le 1000\)
• \(1 \le u_i, v_i, s_x, s_y, x, y \le n\)

Sample Input 1

9
5 5 7 3
1 2
4 1

Sample Output 1

YES

Sample Input 2

9
5 5 7 3
9 2
9 9

Sample Output 2

NO

Explanation

Ở ví dụ 2, Vua đứng ở góc dưới bên trái nhưng ô đích \((9,9)\) nằm trên đường chéo chính đi qua Hậu tại \((5,5)\) nên bị khống chế, không thể bước vào.

Cho hai số nguyên dương \(a\) và \(b\). Hãy viết hàm đệ quy tìm ước chung lớn nhất (gcd) của chúng, chẳng hạn dựa trên thuật toán Euclid: \(\gcd(a, 0) = a\) và \(\gcd(a, b) = \gcd(b, a \bmod b)\).

Input

Một dòng gồm hai số nguyên dương \(a\) và \(b\).

Output

In ra ước chung lớn nhất của \(a\) và \(b\).

Constraints

• \(1 \le a, b \le 10^{18}\)

Sample Input 1

84 36

Sample Output 1

12

Sample Input 2

100 75

Sample Output 2

25

Cho hai số nguyên dương \(x\) và \(y\). Ta tạo ra một số mới \(z\) bằng cách xen kẽ các chữ số của \(x\) và \(y\) theo thứ tự tuỳ ý, miễn là các chữ số của \(x\) vẫn xuất hiện trong \(z\) theo đúng thứ tự cũ, và các chữ số của \(y\) cũng vậy. Nói cách khác, \(z\) là một cách "trộn" hai xâu chữ số của \(x\) và \(y\) (như trộn hai xấp bài mà không đảo thứ tự từng xấp).

Hãy tìm giá trị nhỏ nhất và giá trị lớn nhất có thể có của \(z\).

Input

Một dòng gồm hai số nguyên dương \(x\), \(y\).

Output

• Dòng 1: giá trị nhỏ nhất của \(z\).
• Dòng 2: giá trị lớn nhất của \(z\).

Constraints

• \(1 \le x, y \le 10^9\)

Sample Input 1

57 402

Sample Output 1

40257
57402

Sample Input 2

90 8

Sample Output 2

890
980

Explanation

Ở ví dụ 2, các cách ghép là \(908\), \(980\), \(890\); nhỏ nhất là \(890\) và lớn nhất là \(980\).

Với số nguyên không âm \(n\), gọi \(\mathrm{Fsum}(n)\) là tổng các chữ số thập phân của \(n\) (với \(n = 0\) thì \(\mathrm{Fsum}(0) = 0\)). Ví dụ \(\mathrm{Fsum}(408) = 4 + 0 + 8 = 12\).

Hãy viết hàm đệ quy tính \(\mathrm{Fsum}(n)\).

Input

Một số nguyên \(n\).

Output

In ra \(\mathrm{Fsum}(n)\).

Constraints

• \(0 \le n \le 10^{18}\)

Sample Input 1

90512

Sample Output 1

17

Sample Input 2

7071

Sample Output 2

15