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 nhập vào từ file văn bản MAXPRO.INP:

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

Kết quả ghi ra file văn bản MAXPRO.OUT:

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}.~

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 nhập vào từ file văn bản VOTE.INP:

• 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ả ghi ra file văn bản VOTE.OUT:

• 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.~

Cho một bảng hình chữ nhật có ~N~ dòng và ~M~ cột gồm các chữ cái in thường từ ~'a'~ đến ~'z'~. Bảng này có tính chất: ở mỗi cột, khi ghép các kí tự từ trên xuống dưới sẽ thu được một xâu đại diện và trong bảng các xâu đại diện là đôi một khác nhau.

Yêu cầu: Hãy tìm cách xoá nhiều nhất các dòng (lần lượt từ dòng đầu tiên xuống dưới) của bảng để thu được một bảng mới vẫn đảm bảo tính chất trên. (Chỉ được xoá tối đa ~N-1~ dòng)

Dữ liệu nhập vào từ file văn bản DELROW.INP:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ cách nhau một dấu cách~;~
• ~N~ dòng sau, mỗi dòng chứa một xâu có dộ dài ~M.~

Kết quả ghi ra file văn bản DELROW.OUT:

Gồm một số duy nhất là kết quả của bài toán.

Ví dụ

Input

5 4
qwpt
abcf
bvoa
abka
bbhb

Output

2

Giải thích:

Xoá tối đa ~2~ dòng đầu. Nếu xoá cả dòng thứ ~3~ thì cột đầu tiên và cột cuối cùng sẽ giống nhau. (không thoả mãn tính chất của bảng)

Giới hạn

• Có ~40\%~ số test tương ứng với số điểm có ~N,M≤100;~
• ~30\%~ số test khác tương ứng với số điểm có ~N,M≤500;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~N,M≤5000.~

Thao tác tăng hình nón đối xứng của một dãy số ~X_1,X_2,X_3,…,X_{N-2},X_{N-1},X_N~ được thực hiện như sau:

• Tăng ~X_1~ và ~X_N~ lên ~1~ đơn vị~;~
• Tăng ~X_2~ và ~X_{N-1}~ lên ~2~ đơn vị~;~
• Tăng ~X_3~ và ~X_{N-2}~ lên ~3~ đơn vị~;~
• ~…~

Cho một bảng hình vuông ~A~ có ~N~ dòng, ~N~ cột. Các dòng được đánh số từ ~1~ tới ~N~ theo thứ tự từ trên xuống dưới và các cột được đánh số từ ~1~ tới ~N~ theo thứ tự từ trái qua phải. Ô ở dòng thứ ~i~, cột thứ ~j~ được gọi là ô ~A(i,j)~. Ban đầu tất cả các ô đều có giá trị bằng ~0~. Thực hiện ~T~ thao tác tăng hình nón đối xứng trên bảng ~A~, mỗi thao tác có cấu trúc như sau: gồm bốn số nguyên dương ~k,rc,x,y~ ~(k=1~ hoặc ~k=2)~ có ý nghĩa:

• Khi ~k = 1,~ thực hiện tăng hình nón đối xứng trên dòng ~rc~ với dãy số gồm các số từ ~A(rc,x)~ đến ~A(rc,y);~
• Khi ~k = 2,~ thực hiện tăng hình nón đối xứng trên cột ~rc~ với dãy số gồm các số từ ~A(x,rc)~ đến ~A(y,rc)~.

Yêu cầu: Cho kích thước bảng, ~T~ thao tác tăng và ~Q~ câu hỏi. Mỗi câu hỏi có ý nghĩa: tìm giá trị của một ô của bảng sau khi thực hiện ~T~ thao tác.

Dữ liệu nhập vào từ file văn bản ITABLE.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~T~ là kích thước của bảng và số thao tác tăng. ~(N≤5000; \ T≤10^5)~
• ~T~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~k,rc,x,y~ mô tả thao tác tăng lên dòng hoặc cột của bảng. ~(k=1~ hoặc ~k=2; \ rc,x,y≤N)~
• Dòng tiếp theo gồm số một số nguyên dương ~Q~ là số ô cần tìm giá trị. ~(Q≤10^5)~
• ~Q~ dòng sau, mỗi dòng chứa hai số nguyên dương ~u,v~ có ý nghĩa là cần tìm giá trị của ô ~A(u,v)~. ~(u,v≤N)~

Mỗi số cách nhau một dấu cách. Dữ liệu đảm bảo đúng đắn và luôn có kết quả.

Kết quả ghi ra file văn bản ITABLE.OUT:

Gồm ~Q~ dòng, mỗi dòng in ra giá trị của một ô tương ứng.

Ví dụ

Input

4 2
1 2 1 4
2 3 1 3
3
1 1
2 2
2 3

Output

0
2
4

Giải thích:

Giới hạn

• Có ~50\%~ số test tương ứng với số điểm có với ~T≤5000;~
• Có ~30\%~ số test khác tương ứng với số điểm có với ~Q≤500;~
• Có ~20\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm~.~