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.

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

Example

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

8
9

Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dòng của ma trận
bên phải. Nếu ma trận \(A\) có kích thước \(m\) x \(n\) và ma trận \(B\) có kích thước \(n\) x \(p\) , thì ma trận
tích C = \(A\) x \(B\) có kích thước \(m\) x \(p\) , phần tử đứng ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

\(c_{i,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j} + \dots + a_{i,n}b_{n,j}\)

Phép nhân ma trận có các tính chất kết hợp: (\(A\) x \(B\)) x \(C\) = \(A\) x (\(B\) x \(C\))

Ví dụ:
\(A = \binom{0, 1}{1, 1}; A^2 = \binom{1, 1}{1, 2}; A^3 = \binom{1, 2}{2, 3}\)

Yêu cầu: Cho ma trận \(A\) kích thước \(n\) x \(n\) và ma trận B, hãy kiểm tra xem \(A^3\) có bằng hay \(B\) không?

Input

• Dòng thứ nhất chứa số nguyên dương \(T\) \((T \leq 20)\) là số lượng bộ dữ liệu;
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm dòng tương ứng với một bộ dữ liệu có dạng:
• Dòng đầu chứa số nguyên \(n\);
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(A\), các số có giá trị tuyệt đối không vượt quá 1000;
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(B\), các số có giá trị tuyệt đối không vượt quá 10^18.

Output

Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với một bộ dữ liệu theo thứ tự xuất hiện trong file dữ liệu vào: ghi thông báo ‘YES’ nếu \(A^3 = B\) và ghi ‘NO’ trong trường hợp ngược lại.

Scoring

• Có \(50\)% số test ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 10\);
• \(50\)% số test còn lại ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 500\).

Example

2
2
0 1 
1 1
1 2
2 2
2
0 1 
1 1
1 2
2 3

NO
YES

Cho chuỗi kí tự \(s\) có độ dài \(n\) chỉ bao gồm các kí tự in thường. Các kí tự được đánh số từ 0 đến \(n - 1\), \(s = s_0,s_1,\dots,s_{n-1}\)

Chuỗi này sẽ được áp dụng lần lượt các thao tác thay đổi \((i,j,c_1,c_2)\) là biến đổi các vị trí là kí tự \(c_1\) thành kí tự \(c_2\) trong đoạn từ \(i\) đến \(j\).

Yêu cầu: Cho biết chuỗi \(s\) ban đầu và \(m\) thao tác biến đổi, hãy đưa ra chuỗi cuối cùng sau biến đổi.

Input

• Dòng đầu chứa chuỗi \(s\) có độ dài \(n\) \((1 \leq n \leq 10^6)\), xâu \(s\) chỉ chứa kí tự thường;
• Dòng thứ hai chứa số \(m\) \((1 \leq m \leq 1.5 \times 10^5)\)
• \(m\) dòng tiếp theo mỗi dòng chứa \(i, j, c_1, c_2\) \((0 \leq i \leq j < n; c_1 \neq c_2)\)

Output

Ghi ra thiết bị ra chuẩn xâu \(s\) sau biến đổi.

Scoring

• Có \(20\)% số test ứng với \(20\)% số điểm của bài có \(n, m \le 2000\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có \(n, m \leq 5 \times 10^4\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có \(n \leq 3 \times 10^5\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có các kí tự trong xâu và biến đổi chỉ là \('a'\) hoặc \('b'\);
• Có \(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

Example

aaaabbbbcccc
3
0 2 a y
5 9 b c
1 3 a z

yyyzbccccccc