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:

• Một dòng duy nhất gồm bốn số nguyên ~a, b, c, M~.

Kết quả:

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

Ví dụ:

Sample Input 1

3 2 5 4

Sample Output 1

3

Sample Input 2

2 -3 -2 100

Sample Output 2

6

Ràng buộc:

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

Chuẩn bị Gala mừng ngày thành lập 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 \le N \le 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 \le N \le 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.

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ụ:

Sample 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

Sample 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.

Ràng buộc:

• Có ~70\%~ số test tương ứng với ~70\%~ số điểm có ~N \le 1000~;
• Có ~30\%~ số test còn lại tương ứng với ~30\%~ 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:

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

Kết quả:

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

Ví dụ:

Sample Input

5 4
qwpt
abcf
bvoa
abka
bbhb

Sample 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 ~40\%~ số điểm có ~N, M \le 100~;
• Có ~30\%~ số test khác tương ứng với ~30\%~ số điểm có ~N, M \le 500~;
• Có ~30\%~ số test còn lại tương ứng với ~30\%~ số điểm có ~N, M \le 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:

• 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 \le 5000;T \le 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 \le 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 \le 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 \le N~).

Dữ liệu đảm bảo đúng đắn và luôn có kết quả.

Kết quả:

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

Ví dụ:

Sample Input

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

Sample Output

0
2
4

Giải thích:

Ràng buộc:

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