Bài tập

Cho bảng chữ kích thước \(m \cdot n\), mỗi ô chứa một kí tự \(A\) hoặc \(B\). Một hình chữ nhật con của bảng được gọi là bảng đẹp bậc \(k\) nếu số lượng kí tự \(A\) và số lượng kí tự \(B\) trong bảng con chênh lệch không quá \(k\).

Yêu cầu:
Cho bảng chữ kích thước \(m \cdot n\) và số nguyên \(k\), hãy tìm bảng con là bảng đẹp lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T(T \leq 5)\) là số bộ dữ liệu.

• \(T\) nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:

• Dòng đầu chứa ba số nguyên \(m, n, k\).

• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\) chỉ gồm kí tự \(A\) hoặc \(B\).

Output

• Ghi ra thiết bị ra chuẩn \(T\) dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được
  tương ứng với dữ liệu vào.

Example

2
3 4 0
AAAA
BBBB
BAAA
3 4 1
AAAA
BBBB
BAAA

8
9

Scoring

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 100\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 2000\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 40000, k = 0\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 60000\).

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Hãy loại một phần tử bất kỳ trong dãy số và đặt \(P\) tích các số còn lại. Phân tích thừa số nguyên tố của \(P\), sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm \(4\) số \(1; 2; 4; 10\). có 2 cách bỏ đều cho tổng số mũ bằng \(3\) là nhỏ nhất:

• Cách 1: Loại bỏ số \(4\), ta có \(P=1 * 2*10=20=2^2*5\) có tổng số mũ bẳng \(3\)

• Cách 2: Loại bỏ số \(10,\) ta có \(P=1 * 2*4=8=2^3\) có tổng số mũ bẳng \(3\)

Yêu cầu: Cho dãy số \(A\), hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Input

• Dòng đầu tiên chứa dãy số \(n (n≤10^5)\).

• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A (A_i≤10^6)\).

Output

Một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Example

4
1 2 4 10

3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤3\).

• Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤8\).

• Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤10^6\).

• Subtask \(4\) (\(10\%\) số điểm): trường hợp còn lại.

Xét dãy vô hạn các số tự nhiên liên tiếp bắt đầu từ \(1\): \(1, 2, 3,...\) và \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\). Trên dãy vô hạn các số tự nhiên này, tiến hành xóa hết các số chia hết cho \(a_{1}\), sau đó xóa hết các số chia hết cho \(a_{2}\) mà chưa được xóa,..., cuối cùng xóa hết các số chia hết cho \(a_{n}\) mà chưa được xóa. Đánh số các số chưa được xóa bắt đầu từ \(1\), người ta muốn biết số được đánh số thứ \(k\) là số nào?

Yêu cầu: Cho dãy số \(a_{1}, a_{2}, ..., a_{n}\) và \(k\), hãy tìm số tự nhiên được đánh số thứ \(k\) trên dãy sau khi xóa.

Input

--- Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu;

--- \(T\) nhóm dòng sau, mỗi nhóm có dạng:

o Dòng đầu của nhóm chứa hai số nguyên dương \(n\) và \(k\) \((1 ≤ k ≤ 10^{15})\);

o Dòng thứ hai của nhóm chứa \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\) \((1 < a_{i} ≤ 10^{15})\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số tự nhiên là kết quả tương ứng của bộ test trong dữ liệu vào.

Example

1
2 5
3 4

10

Scoring

\(30\%\) số test có \(n = 1\)

\(30\%\) số test có \(n = 2\)

\(40\%\) số test có \(n \leq 10\)

Những người làm vườn có kinh nghiệm nhận thấy rằng nếu một quả cà chua chín đỏ (R) được đặt giữa những quả cà chua xanh (G) đã hái thì những quả cà chua xanh lân cận sẽ chín sau đúng một ngày.

Có \(n\) quả cà chua được xếp cạnh nhau thành một hàng, đánh số từ \(1\) đến \(n\).
Ba trong số những quả cà chua này đã chín, vị trí của chúng trong hàng là \(m_1, m_2, m_3\).

Yêu cầu: Hãy tìm số cà chua xanh còn lại sau \(d\) ngày.

Input

• Đọc từ tệp văn bản CAU1.INP gồm một dòng chứa năm số nguyên \(n, m_1, m_2, m_3, d\) \((4 \leq n \leq 10^{16}, 1 \leq m_i \leq n, i = 1,2,3, 1 \leq d \leq 10^{16})\).

• Các số cách nhau bởi dấu cách.

Output

• Ghi ra tệp văn bản CAU1.OUT gồm một dòng ghi một số là số cà chua xanh còn lại sau \(d\) ngày.

Example

19 2 13 15 2

8

50 1 50 25 7

19

Scoring

• \(50\%\) số điểm có \(n \leq 10^9\).

• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.