HSG THCS Hà Nội 2021

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\).

Input

• Gồm bốn số nguyên \(a, b, c, M\).
• Các số cách nhau một dấu cách.

Output

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

Example

3 2 5 4

3

2 -3 -2 100

6

Scoring

• \(70\%\) số test tương ứng với số điểm có \(|a|, |b|, |c| \leq 10^9\), \(1 \leq M \leq 10^9\).
• \(30\%\) số test còn lại tương ứng với số điểm có \(|a|, |b|, |c| \leq 10^{18}\), \(1 \leq M \leq 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 \leq N \leq 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.

Input

• Dòng đầu tiên gồm số một số nguyên dương \(N\) (\(1 \leq N \leq 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.

Output

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

Example

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

2 3
3 4

Scoring

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

Input

• 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ài \(M\).

Output

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

Example

5 4
qwpt
abcf
bvoa
abka
bbhb

2

Scoring

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

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.

Input

• 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 \leq 5000\); \(T \leq 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 \leq N\))
• Dòng tiếp theo gồm một số nguyên dương \(Q\) là số ô cần tìm giá trị. (\(Q \leq 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 \leq 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ả.

Output

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

Example

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

0
2
4

Scoring

• Có \(50\%\) số test tương ứng với số điểm có với \(T \leq 5000\).
• Có \(30\%\) số test khác tương ứng với số điểm có với \(Q \leq 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.