Bài tập

Thầy Phú xếp \(N\) học sinh thành một hàng để phát kẹo. Bạn đầu hàng nhận \(1\) viên, các bạn tiếp theo lần lượt nhận nhiều hơn bạn ngay trước đúng \(3\) viên (dãy \(1, 4, 7, 10, \dots\)). Thầy phát lần lượt từ đầu hàng và chỉ phát khi số kẹo còn lại đủ cho bạn đó theo đúng quy tắc; ngay khi không đủ, thầy dừng lại (không phát thêm cho ai nữa, số kẹo dư thầy đem về).

Thầy chỉ có \(K\) viên kẹo. Hãy tính số học sinh nhận được kẹo.

Input

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

Output

• In ra một số nguyên là số học sinh nhận được kẹo.

Constraints

• \(1 \le N \le 10^{5}\).
• \(1 \le K \le 10^{15}\).

Sample Input 1

5 30

Sample Output 1

4

Sample Input 2

4 100

Sample Output 2

4

Explanation

Ở ví dụ 1, bốn bạn đầu cần \(1+4+7+10 = 22 \le 30\) viên, bạn thứ năm cần thêm \(13\) viên nên \(35 > 30\): dừng lại. Ở ví dụ 2, kẹo còn dư nhưng lớp chỉ có \(4\) bạn.

Sắn và Mì chơi một trò với \(N\) quân bài, quân bài thứ \(i\) ghi số \(S_i\). Các lượt bốc diễn ra như sau: Sắn bốc \(1\) quân, sau đó Mì bốc \(2\) quân, rồi Sắn bốc \(2\) quân, rồi Mì bốc \(2\) quân, và cứ thế luân phiên (mỗi lần trừ lần đầu là \(2\) quân) cho đến khi hết bài. Ở mỗi lượt, người chơi được tự chọn quân bài bất kỳ còn trên bàn; nếu còn ít quân hơn số cần bốc thì bốc hết số còn lại. Cả hai đều chơi tối ưu để tổng số trên các quân mình bốc được là lớn nhất.

Người có tổng lớn hơn thắng. Hãy cho biết kết quả của Sắn: THANG nếu Sắn thắng, HOA nếu hai tổng bằng nhau, THUA nếu Sắn thua.

Input

• Dòng đầu: số nguyên \(N\).
• Dòng sau: \(N\) số nguyên \(S_1, \dots, S_N\).

Output

Một dòng duy nhất: THANG, HOA hoặc THUA.

Constraints

• \(1 \le N \le 10^6\)
• \(0 \le S_i \le 10^9\)

Sample Input

4
8 3 9 5

Sample Output

THUA

Explanation

Sắn bốc \(9\); Mì bốc \(8\) và \(5\) được \(13\); Sắn bốc nốt \(3\) được \(12\). Vì \(12 < 13\) nên Sắn thua.

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