Giới thiệu: Đây là đề Training Python 3

Cho mảng số nguyên ~A~ có ~n~ phần tử được nhập từ bàn phím. Hãy viết chương trình tìm ~3~ phần tử ở các vị trí khác nhau trong mảng sao cho tích của ~3~ phần tử đó là lớn nhất. Sau đó, hãy in giá trị tích lớn nhất mà bạn tìm được lên màn hình.

Input

Dòng ~1~ là số lượng phần tử của mảng ~n~. Dòng tiếp theo là ~n~ số nguyên tương ứng là các phần tử của mảng.

Output

Tích lớn nhất mà bạn tìm được.

Examples

Input

5
1 2 3 4 5

Output

60

Giới thiệu: Đây là đề Training Python 3

Cho mảng số nguyên ~A~ có ~n~ phần tử, hãy tìm ~2~ phần tử lân cận trong mảng sao cho tổng của chúng là lớn nhất. Giả sử phần tử cuối cùng và phần tử đầu tiên cũng có tính lân cận (tạo thành vòng tròn khép kín)

Input

Cho mảng số nguyên ~A~ có ~n~ phần tử, hãy tìm ~2~ phần tử lân cận trong mảng sao cho tổng của chúng là lớn nhất. Giả sử phần tử cuối cùng và phần tử đầu tiên cũng có tính lân cận (tạo thành vòng tròn khép kín)

Output

In ra ~2~ phần tử lân cận nhau (cách nhau bởi ~1~ dấu cách) thỏa mãn yêu cầu đề bài.

Examples 1

Input

5
3 2 -1 2 4

Output

4 3

Examples 2

Input

6
1 2 6 1 6 2

Output

6 2

Note

Giữ nguyên thứ tự ban đầu của chúng

Nếu có nhiều kết quả, in ra kết quả ở cặp có chỉ số mảng (của phần tử đầu tiên) lớn hơn.

Giới thiệu: Đây là đề Training Python 3

Số nguyên tố hay còn gọi là hợp số, đây là tập hợp số tự nhiên chỉ chia hết cho ~1~ và chính nó. Nhập vào một số nguyên dương ~N~, hãy phân tích số ~N~ thành tích các thừa số nguyên tố

Input

Số nguyên dương ~N~

Output

~1~ dòng duy nhất là tích của các thừa số nguyên tố (các thừa số theo thứ tự từ bé đến lớn). Nếu không có thừa số in ra rỗng " " (không có dấu ngoặc kép)

Examples

Input

456

Output

2*2*2*3*19

Giới thiệu: Đây là đề Training Python 3

Hôm nay, Nhi lên H2.2 chơi thì phát hiện trên bàn có một chuỗi ~t~. Nhi đặc biệt thích kí tự '~n~'. Nhi gọi một chuỗi là đặc biệt nếu chuỗi đó có đúng hơn ~1~ nửa số ký tự trong chuỗi là kí tự '~n~'. Ví dụ "~nnnbb~" hoặc "~nann~" là một chuỗi đặc biệt tuy nhiên chuỗi '~lnln~' hoặc chuỗi rỗng thì không phải chuỗi đặc biệt.

Nhi quyết định xóa một vài kí tự ra khỏi chuỗi. Nhi muốn biết sau khi xóa một số kí tự (có thể là không xóa kí tự nào) để có được chuỗi đặc biệt thì chuỗi còn bao nhiêu kí tự.

Input

Dòng duy nhất chứa chuỗi ~t~, ~1 \le t \le 50~ gồm các kí tự tiếng anh viết thường (nghĩa là không có ă, ấ, ơ, ....) luôn đảm bảo rằng có kí tự 'n' trong chuỗi ~t~ (nếu không có kí tự 'n' in ra -1).

Output

In ra 1 số nguyên duy nhất là độ dài của chuỗi đặc biệt dài nhất mà Nhi có được sau khi xóa một vài kí tự khỏi chuỗi t

Examples 1

Input

anaaaan

Output

3

Examples 2

Input

nnnbnn

Output

6

Đây là đề Training Python 3

Ở vương quốc BULCIA mọi người rất thích những con số may mắn (những con số mà chúng chỉ chứa số ~4~ và số ~7~). Ví dụ, số ~47~, ~477~, ~74~ là những số may mắn và ~5~, ~467~, ~17~ không phải là những con số may mắn.

Và họ gọi một số là suýt may mắn nếu nó có thể chia hết cho một số may mắn. Hãy giúp người dân BULCIA kiểm tra xem số tự nhiên ~n~ có phải là số suýt may mắn không?

Input

~1~ dòng duy nhất một số tự nhiên ~n~ ~(1 \le n \le 1000)~

Output

Trong dòng duy nhất in YES, nếu số ~n~ là số may mắn hoặc là số suýt may mắn. Nếu không, hãy in NO.

Examples 1

Input

47

Output

YES

Examples 2

Input

16

Output

YES

Examples 3

Input

78

Output

NO

Giới thiệu: Đây là đề Training Python 3

Nam hay sử dụng mạng xã hội để giết thời gian. Trong trang danh sách trò chuyện, khi Nam gửi tin nhắn đến một người bạn nào đó, thì cuộc trò chuyện của người bạn đó sẽ xuất hiện ở đầu trang. Thứ tự đối với các cuộc trò chuyện khác không thay đổi. Trong trường hợp nếu không có cuộc trò chuyện nào với người bạn này trước đó, thì cuộc trò chuyện mới sẽ được chèn vào đầu danh sách trò chuyện.

Giả sử rằng Nam chưa có cuộc trò chuyện nào trước đó, và Nam tạo một danh sách các cuộc trò chuyện sau khi tất cả các tin nhắn của anh ấy đã được gửi đi thành công. Giả sử không có người bạn nào nhắn bất kì tin nhắn nào cho Nam.

Input

Dòng đầu tiên chứa 1 số ~n~ ~(1 \le n \le 200 000)~ - số tin nhắn mà Nam gửi.

~n~ dòng tiếp theo hiển thị người nhận tin nhắn được sắp xếp theo thứ tự tin nhắn được gửi. Tên của mỗi người tham gia cuộc trò chuyện là một dãy kí tự gồm các chữ cái tiếng Anh viết thường có độ dài tối đa là ~10~ kí tự.

Output

In tất cả những người mà Nam đã nói chuyện theo thứ tự các cuộc trò chuyện từ trên xuống dưới.

Examples 1

Input

4
alex
ivan
roman
ivan

Output

ivan
roman
alex

Examples 2

Input

8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Output

alina
maria
ekaterina
darya

Note

Trong test case 1, Nam gửi tin nhắn cho bạn có tên "alex", danh sách chat của Nam sẽ hiển thị như sau:

1. alex

Sau đó Nam gửi tin nhắn cho bạn "ivan", danh sách chat của Nam sẽ hiển thị như sau:

1. ivan
2. alex

Nam gửi tin nhắn thứ 3 cho người bạn tên "roman", danh sách trò chuyện của Nam sẽ được hiển thị như sau:

1. roman
2. ivan
3. alex

Nam viết tin nhắn thứ tư cho bạn bè bằng tên "ivan", cho người mà anh ta đã gửi tin nhắn, vì vậy danh sách các cuộc trò chuyện thay đổi như sau:

1. ivan
2. roman
3. alex

Hot boi CheeseTrung vừa đẹp trai, lại vừa giỏi lập trình nên rất được các bạn nữ thích, đặc biệt là các bạn K17. Được biết anh rất thích ăn mì, nhưng chỉ có 4 bạn biết điều đó. 4 bạn ấy đã thành lập 1 cuộc thi xem ai nấu mì giỏi nhất.

Cách thi như sau: bạn thứ nhất sẽ đấu với bạn thứ hai, 2 bạn còn lại sẽ đấu với nhau. Trong 2 cặp đấu sẽ lần lượt chọn được 2 tô mì có độ ngon nhất và sẽ được CheeseTrung ăn thử.

Độ ngon của tô mì được làm bởi bạn nữ thứ i-th sẽ bằng với si và tất cả các độ ngon của các tô mì đều khác nhau. Tô mì nào có độ ngon lớn hơn sẽ thắng.

Những hỡi ôi, CheeseTrung chỉ quan tâm tới mì thôi. Anh muốn bạn cho anh ấy biết, với cách thi đấu như vậy, thì liệu anh ấy có cơ hội để ăn 2 tô mì có độ ngon lớn nhất trong cuộc thi này không.

Xác định xem CheeseTrung có cơ hội như thế không.

Input
Dòng thứ nhất chứa 1 số nguyên t (1≤t≤~10^4~) — số lượng các test cases.

Mỗi test case chỉ chứa 1 dòng duy nhất, dòng đó chứa bốn số nguyên ~s_1~,~s_2~,~s_3~,~s_4 ~(1 ≤ ~s_i~ ≤ 100) — độ ngon của các tô mì. Biết rằng 4 số này là chắc chắn khác nhau.

Output
Mỗi test case chỉ in ra 1 từ duy nhất, YES nếu CheeseTrung có cơ hội như thế hoặc NO nếu ngược lại.

Examples
Input

4
3 7 9 5
4 5 6 9
5 3 8 1
6 5 3 2

Output

YES
NO
YES
NO

Note

1. Trong test case 1, 2 bạn nữ thứ 2 và 3 nấu tô mì có độ ngon lần lượt là 7 và 9 và CheeseTrung đã có cơ hội để ăn;
2. Trong test case 2, 2 bạn nữ thứ 2 và 4 nấu tô mì có độ ngon lần lượt là 5 và 9 được CheeseTrung ăn thử. Tuy nhiên đây không phải 2 tô mì có độ ngon lớn nhất cuộc thi;

Đây là đề Training Python 3

Hôm nay, bạn Cốc đố bạn Huề một bài toán sau.

Có ~n~ con mèo ăn n gói pate. Có ba loại mèo tất cả. Mèo xám ăn ~5~ gói, mèo vàng ăn tận ~3~ gói. Mèo mun vì nhường các bạn nên đành ăn ít hơn chỉ ăn 1/3 gói pate. Hỏi với mỗi loại mèo có bao nhiêu con????

hmm, suy nghĩ nửa ngày trời mà Huề vẫn chưa giải được và tìm câu trả lời. Bạn sẽ giúp Huề chứ ??

Input

Số nguyên ~n~ là số lượng mèo và số gói pate ~(n \le 250)~

Output

In ra tất cả các trường hợp số lượng mèo xám, số lượng mèo vàng, số lượng mèo mun nếu thỏa mãn điều kiện, nếu không in ra -1. Mỗi dòng là mỗi trường hợp và mỗi trường hợp xuất ra trên một dòng và số lượng mèo xám, số lượng mèo vàng, số lượng mèo mun cách nhau bởi 1 khoảng trắng.

Examples 1

Input

100

Output

4 18 78
8 11 81
12 4 84

Examples 2

Input

20

Output

-1