Nhân dịp Giáng sinh, An muốn tự làm một chiếc bánh kem thật đẹp để trang trí cho buổi lễ. An muốn để chiếc bánh kem trên mặt bàn hình tròn ở phòng khách. Tuy nhiên nhà An chỉ có khuôn làm được chiếc bánh kem hình chữ nhật có kích thước ~a \times b~, An băn khoăn rằng với chiếc bánh kem kích thước ~a \times b~ có thể đặt lên mặt bàn hình tròn bán kính ~r~ mà không có phần nào của bánh bị tràn ra ngoài biên của mặt bàn hay không.

Yêu cầu

Với ba số ~r,\ a,\ b~ tương ứng là bán kính của mặt bàn và kích thước chiếc bánh kem. Bạn hãy cho biết có thể đặt chiếc bánh kem lên mặt bàn hình tròn hay không?

Dữ liệu đầu vào

Gồm ba số ~r,\ a,\ b~ ~(r, a, b \le 10^3)~, các số cách nhau một dấu cách tương ứng là bán kính của mặt bàn, kích thước của chiếc bánh.

Dữ liệu đầu ra

Ghi YES/NO tương ứng với CÓ/KHÔNG.

Ví dụ

Ví dụ 1

INPUT

3 3 4

OUTPUT

YES

Ví dụ 2

INPUT

1 3 4

OUTPUT

NO

Trong giờ Tin học của lớp 9A thầy Minh có đưa ra một trò chơi trúng thưởng như sau:

Thầy viết lên bảng một xâu ~S~, bạn nào tìm ra số nguyên tố lớn nhất có trong xâu ~S~ sẽ nhận được phần thưởng.

Yêu cầu

Xâu ~S~ gồm ~N~ ký tự chỉ chứa chữ cái và chữ số, học sinh cần chọn một đoạn con liên tiếp chỉ gồm các chữ số để tạo thành một số không quá ~5 \times 10^6~ và là số nguyên tố. Học sinh chọn được số nguyên tố lớn nhất sẽ được tặng thưởng số tiền bằng đúng số được chọn. Bạn hãy giúp các học sinh chọn ra số nguyên tố lớn nhất để nhất để nhận được nhiều tiền thưởng nhất có thể.

Ví dụ: ~S =~ cd0056a845k1250cd19hk23, ta có thể tạo ra các số như: ~0, 00, 005, 0056, 0, 05, 056, 5, 564, 45, 5, ...~ tuy nhiên chỉ có các số ~2, 3, 5, 19, 23~ là các số nguyên tố, nên số tiền nhận được là ~23~.

Dữ liệu đầu vào

Gồm một xâu ~S~ có độ dài không quá ~5 \times 10^6~ kí tự.

Dữ liệu đầu ra

Gồm một số nguyên là số tiền mà học sinh nhận được. Nếu không có số nguyên tố nào thì số tiền nhận được là ~0~.

Ràng buộc dữ liệu

• 75% test ứng với 75% số điểm với ~1 \le N \le 255~, số nguyên tố lớn nhất tạo được ~\le 10^6~;
• 25% test ứng với 25% số điểm với ~N \le 5 \times 10^6~, số nguyên tố lớn nhất tạo được ~\le 5 \times 10^6~.

Ví dụ

Ví dụ 1

INPUT

cd0056aB45k1250cd19hk23

OUTPUT

23

Ví dụ 2

INPUT

cA1cg4m

OUTPUT

0

Ngày hội đọc sách được tổ chức định kỳ tại trường THCS A. Mỗi quyển sách trong thư viện trường có một "điểm số" đại diện cho độ phổ biến của nó. Có ~n~ quyển sách trong thư viện được đánh số thứ tự từ ~1~ đến ~n~ tương ứng với điểm số là các số nguyên ~A_{1}, A_{2}, ..., A_n~.

Một đoạn con ~[h; r]~ là một dãy các điểm số liên tiếp ~A_h, A_{h + 1}, ..., A_r~ ~(1 \le h \le r \le n)~. Đoạn ~[h; r]~ được gọi là một đoạn điểm số đặc biệt nếu ~A_{h} = A_{r}~ và tổng các điểm số của đoạn này là lớn nhất.

Yêu cầu

Hãy đưa ra tổng của đoạn điểm số đặc biệt.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên ghi số nguyên dương ~n~ là số lượng quyển sách;
• Dòng thứ hai ghi ~n~ số nguyên ~A_1, A_2, ..., A_n~ ~(|A_i| \le 10^3,\ 1 \le i \le n \le 5 \times 10^5)~, mỗi số cách nhau bởi một khoảng trắng.

Dữ liệu đầu ra

Gồm một số nguyên là kết quả theo yêu cầu của bài toán.

Ràng buộc dữ liệu

• Có 30% số test với ~1 \le n \le 10^2~;
• Có 40% số test với ~n \le 5 \times 10^5;\ 0 < A_i \le 10^3;\ \forall\ i \in [1, n]~;
• Có 30% số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

8
5 3 10 3 2 -1 2 9

OUTPUT

16

Ví dụ 2

INPUT

6
5 20 6 1 2 6

OUTPUT

20

Hôm nay cô giáo B dạy học sinh về dãy con tăng dài nhất. Dãy con tăng dài nhất là dãy con nhận được từ dãy ban đầu bằng cách xoá đi một số số, giữ nguyên thứ tự ban đầu, sao cho dãy còn lại thoả mãn tính chất hai số cạnh nhau thì số đứng trước nhỏ hơn số đứng sau.

Sau khi dạy xong, cô giáo B thấy rằng một số số xuất hiện trong nhiều dãy con tăng dài nhất, cô gọi đó là số đặc biệt.

Cho dãy số nguyên ~a_1, a_2, ..., a_n~ khác nhau từng đôi một ~(n \le 10^5,\ 1 \le a_i \le n)~. Số ~a_i~ được gọi là một số đặc biệt đối với dãy số trên nếu như ~a_i~ thuộc ít nhất một dãy con tăng dài nhất của ~A~.

Yêu cầu

Tìm các số đặc biệt của dãy ~A~.

Dữ liệu đầu vào

Gồm ~2 \times T + 1~ dòng:

• Dòng đầu ghi ~T~ ~(1 \le T \le 10)~ là số bộ test.
• ~T~ nhóm dòng tiếp theo, mỗi nhóm gồm hai dòng: Dòng thứ nhất là số ~n~, dòng thứ hai là ~n~ số nguyên có thứ tự từ ~1~ đến ~n~.

Dữ liệu đầu ra

Gồm ~T~ dòng, mỗi dòng ghi các số đặc biệt của bộ test tương ứng theo giá trị tăng dần.

Ràng buộc dữ liệu

• Có 60% số test có ~n \le 10^2~;
• Có 40% số test còn lại có ~n \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

2
7
1 2 3 7 4 5 6
5
1 4 3 2 5

OUTPUT

1 2 3 4 5 6
1 2 3 4 5