Max và Mel là hai tín đồ điện ảnh cuồng nhiệt. Cả hai đều đã xem toàn bộ các bộ phim mà các reviewer nói trong các clip của họ.

Trong năm vừa qua, Max đã xem ~t_1~ trailer, ~e_1~ tập phim bộ và ~f_1~ bộ phim lẻ. Mel đã xem ~t_2~ trailer, ~e_2~ tập phim bộ và ~f_2~ bộ phim lẻ. Mỗi trailer dài ~3~ phút, mỗi tập phim bộ dài ~20~ phút, và mỗi bộ phim lẻ dài ~120~ phút.

Yêu cầu

Hãy xác định ai là người đã xem tổng cộng nhiều phút video hơn trong năm vừa qua.

Dữ liệu

Dòng đầu tiên chứa ~3~ số nguyên ~t_1, e_1, f_1~ là số lượng trailer, tập phim bộ và bộ phim lẻ mà Max đã xem.

Dòng thứ hai chứa ~3~ số nguyên ~t_2, e_2, f_2~ là số lượng trailer, tập phim bộ và bộ phim lẻ mà Mel đã xem.

Kết quả

In ra ~Max~ nếu Max đã xem tổng cộng nhiều phút hơn Mel.

In ra ~Mel~ nếu Mel đã xem tổng cộng nhiều phút hơn Max.

In ra ~Draw~ nếu cả hai đã xem tổng số phút bằng nhau.

Ví dụ

Ví dụ 1

Input

15 1 3
1 3 3

Output

Max

Ví dụ 2

Input

20 3 0
0 0 1

Output

Draw

Ví dụ 3

Input

1 2 3
3 2 1

Output

Max

Giải thích

Ví dụ 1

Max xem tổng cộng ~15 \cdot 3 + 1 \cdot 20 + 3 \cdot 120 = 425~ phút.

Mel xem tổng cộng ~1 \cdot 3 + 3 \cdot 20 + 3 \cdot 120 = 423~ phút.

Do đó kết quả là ~Max~.

Ví dụ 2

Max xem ~20 \cdot 3 + 3 \cdot 20 + 0 \cdot 120 = 120~ phút.

Mel xem ~0 \cdot 3 + 0 \cdot 20 + 1 \cdot 120 = 120~ phút.

Hai người xem bằng nhau nên kết quả là ~Draw~.

Ví dụ 3

Max xem ~1 \cdot 3 + 2 \cdot 20 + 3 \cdot 120 = 403~ phút.

Mel xem ~3 \cdot 3 + 2 \cdot 20 + 1 \cdot 120 = 169~ phút.

Do đó kết quả là ~Max~.

Ràng buộc và chấm điểm

Ràng buộc

~0 \le t_1, e_1, f_1, t_2, e_2, f_2 \le 1000~

Alice muốn tặng Bob một khối lập phương bằng kính làm quà sinh nhật. Tuy nhiên, cô không tìm được nơi nào bán sẵn. May mắn thay, một người bạn đã đưa cho Alice ~3~ tam giác thủy tinh.

Alice có thể cắt các tam giác này thành các mảnh bằng các đường thẳng, với số lần cắt tùy ý, rồi ghép các mảnh lại để tạo thành một khối lập phương.

Yêu cầu

Nếu có thể tạo thành khối lập phương, hãy in ra độ dài cạnh lớn nhất có thể của khối lập phương đó. Nếu không thể, in ra ~Poor Alice~.

Dữ liệu

Gồm ~3~ dòng, mỗi dòng chứa ~3~ số nguyên là độ dài ba cạnh của một tam giác.

Đảm bảo cả ~3~ tam giác đều tồn tại và không suy biến.

Kết quả

Nếu có thể tạo thành khối lập phương, in ra độ dài cạnh của khối lập phương.

Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ~10^{-6}~.

Nếu không thể, in ra ~Poor Alice~.

Ví dụ

Ví dụ 1

Input

3 4 5
5 12 13
7 24 25

Output

4.4721359549995796

Giải thích

Ví dụ 1

Diện tích ba tam giác lần lượt là ~6~, ~30~, ~84~, nên tổng diện tích là ~120~.

Diện tích toàn phần của khối lập phương cạnh ~s~ là ~6s^2~. Do đó: ~6s^2 = 120 \Rightarrow s^2 = 20 \Rightarrow s = \sqrt{20} = 4.4721359549995796~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le A_i, B_i, C_i \le 10^6~

Alice đang ở trong thư viện và học được khái niệm tiền tố và hậu tố.

Tiền tố là một chuỗi con bắt đầu từ đầu chuỗi. Ví dụ, ~ab~ là tiền tố của ~abacaba~.

Hậu tố là một chuỗi con kết thúc ở cuối chuỗi. Ví dụ, ~25~ là hậu tố của ~ab125~.

Alice nhìn thấy một dãy số và tự hỏi liệu có tồn tại hai số, không nhất thiết khác nhau, sao cho một tiền tố của số thứ nhất bằng một hậu tố của số thứ hai hay không.

Yêu cầu

Tìm một cặp chỉ số ~x, y~ sao cho một tiền tố của ~a_x~ bằng một hậu tố của ~a_y~.

Dữ liệu

Dòng thứ nhất chứa số nguyên ~n~ là số lượng phần tử.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Kết quả

In ra một cặp ~x, y~ thỏa mãn điều kiện.

Nếu không tồn tại, in ra ~-1~.

Ví dụ

Ví dụ 1

Input

5
11 12 13 14 15

Output

3 1

Ví dụ 2

Input

2
123456 123123

Output

1 2

Ví dụ 3

Input

1
1

Output

1 1

Giải thích

Ví dụ 1

Tiền tố của ~a_3 = 13~ là ~1~, hậu tố của ~a_1 = 11~ là ~1~.

Ví dụ 2

Tiền tố của ~a_1 = 123456~ là ~123~, hậu tố của ~a_2 = 123123~ là ~123~.

Ví dụ 3

Tiền tố và hậu tố cùng bằng ~1~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le n \le 1000~

~1 \le a_i \le 10^9~

Alice có ~n~ khối lập phương đồ chơi, trên khối thứ ~i~ có ghi số tự nhiên ~a_i~. Từ các khối này, Alice xây thành một tháp lũy thừa.

Yêu cầu

Tính giá trị của biểu thức ~a_1^{a_2^{a_3^{\cdot^{\cdot^{a_n}}}}} \bmod 3~.

Dữ liệu

Dòng đầu tiên chứa số tự nhiên ~n~.

Dòng thứ hai chứa ~n~ số tự nhiên ~a_i~.

Kết quả

In ra một số nguyên duy nhất là giá trị của biểu thức đã cho theo modulo ~3~.

Ví dụ

Ví dụ 1

Input

3
1 2 3

Output

1

Ví dụ 2

Input

3
2 3 2

Output

2

Giải thích

Ví dụ 1

Ta có ~1^{2^3} = 1~, nên kết quả theo modulo ~3~ là ~1~.

Ví dụ 2

Ta có ~2^{3^2} = 2^9 = 512~, và ~512 \bmod 3 = 2~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le n \le 10^5~

~1 \le a_i \le 10^9~

Trong một cuộc thi đọc sách, có ~K~ học sinh tham gia. Mỗi học sinh cần đọc hết một cuốn sách gồm ~N~ trang nhanh nhất có thể.

Với mỗi học sinh ~i~, em đó đọc với tốc độ ~S_i~ trang mỗi phút, nhưng chỉ có thể đọc liên tục nhiều nhất ~T_i~ phút. Sau mỗi lần đọc liên tục, học sinh phải nghỉ ít nhất ~R_i~ phút rồi mới có thể đọc tiếp.

Yêu cầu

Với từng học sinh, hãy xác định số phút cần thiết để đọc hết cuốn sách. Nếu thời gian thực không phải số nguyên thì in ra kết quả làm tròn lên.

Dữ liệu

Dòng đầu chứa hai số nguyên ~N, K~.

~K~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~S_i, T_i, R_i~.

Kết quả

In ra ~K~ dòng.

Dòng thứ ~i~ là số phút cần thiết để học sinh thứ ~i~ đọc xong cuốn sách, sau khi làm tròn lên.

Ví dụ

Ví dụ ~1~

Input

10 3
2 4 1
6 1 5
3 3 3

Output

6
7
7

Giải thích

Ví dụ ~1~

• Học sinh ~1~ đọc được ~8~ trang trong ~4~ phút, nghỉ ~1~ phút, rồi đọc nốt ~2~ trang trong ~1~ phút. Tổng thời gian là ~6~ phút.
• Học sinh ~2~ đọc được ~6~ trang trong ~1~ phút, nghỉ ~5~ phút, rồi đọc nốt ~4~ trang trong ~\frac{4}{6}~ phút. Tổng thời gian là ~1 + 5 + \frac{4}{6} = \frac{20}{3}~ phút, làm tròn lên thành ~7~.
• Học sinh ~3~ đọc được ~9~ trang trong ~3~ phút, nghỉ ~3~ phút, rồi đọc nốt ~1~ trang trong ~\frac{1}{3}~ phút. Tổng thời gian là ~3 + 3 + \frac{1}{3} = \frac{19}{3}~ phút, làm tròn lên thành ~7~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 100000~
• ~1 \le K \le 1000~
• ~1 \le S_i, T_i, R_i \le 100~

Cho số nguyên dương ~N~.

Yêu cầu

Đếm số lượng cặp số nguyên dương ~A, B~ thỏa mãn ~A^2 = B^2 + N~.

Dữ liệu

Dòng đầu tiên chứa một số nguyên ~N~.

Kết quả

In ra một số nguyên duy nhất là số lượng cặp số nguyên dương ~A, B~ thỏa mãn ~A^2 = B^2 + N~.

Ví dụ

Ví dụ ~1~

Input

15

Output

2

Giải thích

Ví dụ ~1~

Có ~2~ cặp thỏa mãn:

• ~A = 4, B = 1~ vì ~4^2 - 1^2 = 15~
• ~A = 8, B = 7~ vì ~8^2 - 7^2 = 15~

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^{12}~

Chấm điểm

• Subtask ~1~: ~20\%~ số điểm, ~N \le 500~
• Subtask ~2~: ~40\%~ số điểm, ~N \le 10^6~
• Subtask ~3~: ~40\%~ số điểm, không có ràng buộc bổ sung

An sống trên một con đường thẳng, xem như trục số với gốc tọa độ ~O~. Nhà của An ở vị trí ~0~. An có ~N~ người bạn, nhà của họ nằm tại các vị trí ~x_1, x_2, \ldots, x_N~.

Không có hai nhà nào có cùng khoảng cách đến gốc, tức là các giá trị ~|x_i|~ đôi một khác nhau.

An di chuyển với tốc độ ~1~ đơn vị quãng đường trong ~1~ phút và có tối đa ~T~ phút để xuất phát từ nhà mình đi thăm các bạn.

An sẽ thăm các nhà theo quy tắc sau: ở mỗi bước, trong số các nhà chưa thăm, An luôn đi tới nhà có khoảng cách đến gốc ~O~ nhỏ nhất.

Yêu cầu

Hãy xác định số nhà nhiều nhất mà An có thể thăm trong thời gian không vượt quá ~T~.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên ~T~ và ~N~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~x_i~ là vị trí nhà của người bạn thứ ~i~.

Kết quả

In ra một số nguyên duy nhất là số nhà nhiều nhất mà An có thể thăm.

Ví dụ

Ví dụ ~1~

Input

25 5
10
-3
8
-7
1

Output

4

Giải thích

Ví dụ ~1~

Thứ tự thăm nhà theo quy tắc là ~1, -3, -7, 8, 10~ vì ~|1| < |-3| < |-7| < |8| < |10|~.

Thời gian di chuyển để thăm ~4~ nhà đầu tiên là:

• từ ~0~ đến ~1~: ~1~ phút
• từ ~1~ đến ~-3~: ~4~ phút
• từ ~-3~ đến ~-7~: ~4~ phút
• từ ~-7~ đến ~8~: ~15~ phút

Tổng cộng là ~24~ phút.

Nếu đi tiếp từ ~8~ đến ~10~ thì cần thêm ~2~ phút, thành ~26~ phút, lớn hơn ~25~, nên không thể thăm nhà thứ ~5~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 50000~
• ~1 \le T \le 10^9~
• ~-100000 \le x_i \le 100000~
• Các giá trị ~|x_i|~ đôi một khác nhau