Cho ba số nguyên ~a,b,c~ và một số nguyên dương ~M~.

Yêu cầu: Hãy tìm tích lớn nhất được tạo bởi hai trong ba số ~a,b,c~. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho ~M~.

Dữ liệu:

Gồm bốn số nguyên ~a,b,c,M~.

Kết quả:

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Input

3 2 5 4

Output

3

Giải thích:

• Tích lớn nhất: ~3 \times 5=15.~
• ~15~ chia ~4~ dư ~3.~ Kết quả là ~3.~

Input

2 -3 -2 100

Output

6

Giải thích:

• Tích lớn nhất: ~(-2) \times (-3)=6.~
• ~6~ chia ~100~ dư ~6.~ Kết quả là ~6.~

Giới hạn

• Có ~70\%~ số test tương ứng với số điểm có ~|a|,|b|,|c|≤10^9, \ 1≤ M≤10^9;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~|a|,|b|,|c|≤10^{18}, \ 1≤ M≤10^{18}.~

Có hai robot đang chuyển động thẳng đều, cùng chiều trên cùng một con đường, robot thứ nhất đang ở vị trí ~S_1~ đang di chuyển với vận tốc là ~V_1 \ m/s~, robot thứ hai đang ở vị trí ~S_2~ di chuyển với vận tốc là ~V_2 \ m/s~. Hỏi sau bao nhiêu lâu thì hai robot gặp nhau?

Dữ liệu:

• Dòng đầu tiên gồm số nguyên dương ~S_1~ mô tả vị trí của robot thứ nhất~;~
• Dòng thứ hai gồm số nguyên dương ~V_1~ mô tả vận tốc của robot thứ nhất~;~
• Dòng thứ ba gồm số nguyên dương ~S_2~ mô tả vị trí của robot thứ hai~;~
• Dòng thứ tư gồm số nguyên dương ~V_2~ mô tả vận tốc của robot thứ hai.

Các đơn vị khoảng các được tính bằng mét, thời gian được tính bằng giây và ~S_1≠S_2 \ ;~ ~S_1,S_2,V_1,V_2≤10^9~.

Kết quả:

In ra một số nguyên là phần nguyên của kết quả - thời gian mà hai robot gặp nhau. Nếu hai robot không thể gặp nhau thì in ra ~-1~.

Ví dụ

Input

2
5
7
3

Output

2

Giải thích: Sau ~2.5~ giây hai robot sẽ gặp nhau:

• ~2+5 \times 2.5=14.5 ~.
• ~7+3 \times 2.5=14.5~ .

Phần nguyên của ~2.5~ là ~2~.

Input

2
3
7
5

Output

-1

Giải thích: Hai robot càng đi càng xa nhau.

Chuẩn bị Gala mừng năm mới Tết Tân Sửu 2021 của công ty HiTech, ban giám đốc quyết định có giải thưởng đặc biệt cho thành viên của công ty. Sau khi đưa ra các tiêu chí đánh giá, việc bầu chọn sẽ được thực hiện bằng cách tất cả các thành viên sẽ được bỏ phiếu cho nhau.

Hình thức bỏ phiếu được thực hiện thông qua phiếu bầu chọn online. Danh sách các thành viên của công ty được niêm yết và quy định là số thứ tự từ ~1~ đến ~N~ ~(1≤N≤5000),~ tương ứng với ~N~ ô trên phiếu bầu chọn. Sau khi thực hiện, ban tổ chức thu được các danh sách phiếu tương ứng của các thành viên công ty. Trong mỗi phiếu bầu chọn, giá trị ô ở vị trí tương ứng ghi ~'X'~ là bầu chọn cho người đó, ô ghi ~'0'~ là không bầu chọn (coi các trường hợp bầu chọn không hợp lệ là không bầu chọn).

Yêu cầu: Em hãy giúp ban tổ chức đưa ra danh sách các nhân viên có phiếu bầu chọn cao nhất.

Dữ liệu:

• Dòng đầu tiên gồm số một số nguyên dương ~N~ ~(1≤N≤5000)~ là số lượng phiếu bầu chọn.
• ~N~ dòng tiếp theo mỗi dòng tương ứng là ~N~ giá trị của các phiếu đã bầu chọn.

Các kí tự cách nhau một dấu cách.

Kết quả:

• Dòng đầu tiên ghi số lượng người được nhiều phiếu nhất và số lượng phiếu.
• Dòng thứ hai ghi thứ tự tương ứng của những người được cao phiếu nhất đó theo thứ tự tăng dần.

Ví dụ

Input

5
X 0 X 0 X
X 0 0 X X
0 0 X 0 0
0 X 0 X 0
0 0 X X 0

Output

2 3
3 4

Giải thích:

• Người số ~1~ được ~2~ phiếu bầu chọn.
• Người số ~2~ được ~1~ phiếu bầu chọn.
• Người số ~3~ được ~3~ phiếu bầu chọn.
• Người số ~4~ được ~3~ phiếu bầu chọn.
• Người số ~5~ được ~2~ phiếu bầu chọn.
• Người số ~3~ và số ~4~ cùng được số phiếu bầu chọn lớn nhất.

Giới hạn

• Có ~70\%~ số test tương ứng với số điểm có ~N \le 1000;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~N \le 5000.~

Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuỗi ARN đặc biệt được mã hóa bằng một xâu ~S~ gồm các kí tự ~'A', \ 'U', \ 'G', \ 'X'~. Họ muốn cắt từ chuỗi ARN đó một mạch (được mã hóa bằng xâu ~X~ cho trước).

Yêu cầu: Từ chuỗi ARN ~S~ có thể cắt được ra tối đa bao nhiêu đoạn mạch ~X~.

Dữ liệu:

• Dòng đầu tiên gồm một xâu kí tự ~S~ mô tả chuỗi ARN~;~
• Dòng thứ hai gồm một xâu kí tự ~X~ mô tả đoạn mạch cần cắt ra.

Các xâu chỉ gồm các kí tự ~'A', \ 'U', \ 'G', \ 'X'~ và độ dài các xâu không quá ~10^3~ kí tự.

Kết quả:

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Input

AUAUGXXAUGXGX
AUGX

Output

2

Giải thích: AUAUGXXAUGXGX

Input

AAAAA
AAA

Output

1

Giải thích: AAAAA

Input

AGAX
U

Output

0

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ ~'𝐴'~ đến ~'𝑍'~ và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ ~1~ có tên là ~'𝐴'~ và nhảy đến các ô tiếp theo quy luật: lần ~1~ nhảy ~1~ ô, lần ~2~ nhảy ~2~ ô, lần ~3~ nhảy ~3~ ô, ~…~, lần ~𝑁~ nhảy ~𝑁~ ô. Vậy sau ~𝑁~ lần nhảy thì robot đang ở ô nào?

Dữ liệu:

Gồm một số nguyên dương ~N~ là số lần nhảy của robot ~(N \le 10^9)~.

Kết quả:

Một kí tự duy nhất là tên của ô sau ~N~ lần robot nhảy.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^3;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^6;~
• ~20\%~ số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

1

Output

B

Giải thích: Sau ~1~ lần nhảy, robot ở ô thứ ~2~, có tên là kí tự ~B~.

Input

4

Output

K

Giải thích: Sau ~4~ lần nhảy, robot ở ô thứ ~11~, có tên là kí tự ~K~.

Input

7

Output

C

Giải thích: Sau ~7~ lần nhảy, robot ở ô thứ ~29~, có tên là kí tự ~C~.

Dữ liệu đảm bảo để bài luôn có kết quả!

Cho bốn số nguyên dương ~A, B, C, D~. Kiểm tra xem đây có phải độ dài bốn cạnh của HCN không?

Input

Gồm bốn dòng, mô tả bốn số nguyên.

Output

In ra YES nếu là HCN, ngược lại in ra NO.

Sample Test

Input

2
3
3
2

Output

YES

Sample Test2

Input

2
3
3
3

Output

NO

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. In ra độ dài của dãy con liên tiếp đan dấu dài nhất. (Đan dấu là không có hai phần tử nào cạnh nhau mà có cùng dấu)

Input:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N≤10^5)~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1,A_2,…,A_N~ mô tả dãy ~A~ ~(0<|A_i|≤10^9)~.

Output:

Ghi ra một số nguyên duy nhất là độ dài của dãy con liên tiếp đan dấu dài nhất.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N≤10^3~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

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

Output

6

Giải thích

Dãy đan dấu: 3 -1 3 -2 4 -5

Sample Test 2

Input:

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

Output

7

Giải thích

Dãy đan dấu 3 -1 3 -2 4 -5 6

NOTE: Nhầm test ví dụ:

INPUT
6 2
2
4
5
2
9
1

OUTPUT
11