Bài tập

Khu vườn của kiến trúc sư Minh được quy hoạch trên một mặt phẳng dạng lưới có kích thước \(n \times m\). Các ô trên lưới có thể trống (kí hiệu '\(.\)') hoặc đã có một bức tượng đặt sẵn (kí hiệu 'B').

Minh muốn trang trí khu vườn bằng cách xây dựng một hàng rào dọc và một hàng rào ngang để chia khu vườn thành bốn phần. Hàng rào ngang sẽ chạy qua giữa hai hàng, và hàng rào dọc sẽ chạy qua giữa hai cột. Sau khi chia, Minh đếm số lượng bức tượng trong mỗi phần:
\begincenter
\begintabular|l|c| \hline
a & b
\hline
c & d
\hline
\endtabular
\endcenter

với \(a, b, c, d\) lần lượt là số bức tượng ở phần trên-trái, trên-phải, dưới-trái và dưới-phải.

Minh không thể nhớ được cách anh ấy đã đặt hàng rào, nhưng anh ấy có một số câu hỏi liên quan đến số bức tượng ở mỗi phần.

Yêu cầu: Cho trước kích thước khu vườn và vị trí các bức tượng. Với mỗi câu hỏi của Minh, hãy xác định xem có tồn tại một cách đặt hàng rào thỏa mãn số lượng bức tượng ở mỗi phần hay không.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\) (\(1 < n, m \le 1000, 1 \le q \le 10^5\)) lần lượt là số hàng, số cột và số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi \(m\) kí tự mô tả trạng thái của mỗi ô đất: '\(.\)' là ô trống, 'B' là ô có bức tượng.

• \(q\) câu hỏi tiếp theo, mỗi câu hỏi trên hai dòng:

• Dòng đầu tiên chứa 2 số nguyên \(a, b\).

• Dòng thứ hai chứa 2 số nguyên \(c, d\).

  với \(a, b, c, d\) là số lượng bức tượng ở 4 phần tương ứng. Dữ liệu đảm bảo tổng số bức tượng trong câu hỏi không vượt quá tổng số bức tượng trên toàn khu vườn.

Output

• Với mỗi câu hỏi, nếu tồn tại cách chia thỏa mãn thì in ra YES. Ngược lại, in ra NO.

Example

3 4 3
..B.
.BB.
B..B
1 2
1 1
2 1
0 1
3 1
0 1

YES
NO
NO

Scoring

• Subtask 1 (30% số điểm): \(n, m \le 20, q \le 100\).
• Subtask 2 (30% số điểm): \(n \le 20, m \le 100, q \le 10000\).
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm.

Syrjälä, một thành phố sầm uất, đang tổ chức lễ hội lớn nhất trong năm. Tuy nhiên, bạn lại đang ở Metsälä, một vùng đất xa xôi, và cần tìm cách quay về tham dự sự kiện này với chi phí thấp nhất.

Bạn có một tấm "Thẻ Vàng Ưu Đãi", cho phép giảm giá một lần duy nhất trên một chuyến bay bất kỳ. Khi sử dụng thẻ này, giá vé của chuyến bay đó sẽ giảm một nửa (làm tròn xuống số nguyên).

Hãy tìm lộ trình rẻ nhất để quay về Syrjälä từ Metsälä, tận dụng tối đa tấm thẻ ưu đãi của bạn!

Input

Dữ liệu được nhập từ bàn phím với định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 10^5, 1 \leq m \leq 2 \cdot 10^5)\) --- số lượng thành phố và chuyến bay.
• Thành phố số 1 là Syrjälä (điểm đến).
• Thành phố số n là Metsälä (điểm xuất phát).
• Mỗi trong số \(m\) dòng tiếp theo chứa ba số nguyên \(a\), \(b\) và \(c\) \((1 \leq a, b \leq n, 1 \leq c \leq 10^9)\), mô tả một chuyến bay một chiều từ thành phố \(a\) đến thành phố \(b\) với giá vé \(c\).
• Luôn luôn có ít nhất một lộ trình từ Metsälä \((n)\) đến Syrjälä \((1)\).

Output

In một số nguyên duy nhất --- giá của hành trình rẻ nhất có thể đạt được khi sử dụng tối ưu "Thẻ Vàng Ưu Đãi".

Example

3 4
1 2 3
2 3 1
1 3 7
2 1 5

2

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử ban đầu. Bạn cần xử lý \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Truy vấn loại 1: dòng có dạng \(1\ x\) --- nghĩa là gán lại \(a_i := a_i \oplus x\) với mọi \(1 \le i \le n\).
• Truy vấn loại 2: dòng có dạng \(2\ k\) --- nghĩa là in ra phần tử lớn thứ \(k\) trong dãy hiện tại (phần tử lớn thứ nhất là lớn nhất).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(Q\) \((1 \le n, Q \le 10^5)\) --- số phần tử ban đầu và số truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((0 \le a_i < 2^{30})\) --- các phần tử ban đầu của dãy \(A\).

• Mỗi dòng trong \(Q\) dòng tiếp theo chứa một truy vấn theo định dạng:

• \(1\ x\) \((0 \le x < 2^{30})\) --- truy vấn loại 1.

• \(2\ k\) \((1 \le k \le n)\) --- truy vấn loại 2.

Output

• Với mỗi truy vấn loại 2, in ra một dòng chứa số nguyên là phần tử lớn thứ \(k\) hiện tại trong dãy.

Example

5 4
3 2 6 0 2
2 2
1 4
2 2
2 3

3
6
6

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 20 & \(n, Q \le 1000\)

2 & 30 & \(x \le 200\)

3 & 50 & Không có ràng buộc bổ sung

\hline
\endtabular

Trên hòn đảo hình vòng tròn, có \(n\) chiếc rương báu vật xếp thành một vòng. Mỗi chiếc rương được đánh số từ \(0\) đến \(n - 1\) và chứa một số lượng vàng ban đầu là \(a_0, a_1, \ldots, a_{n-1}\).

Cướp biển Lập trình viên rất quan tâm đến giá trị của kho báu và thường xuyên thực hiện các hành động sau:

• inc(lf, rg, v) --- Thêm \(v\) thỏi vàng vào mỗi chiếc rương từ vị trí \(lf\) đến \(rg\) (tính cả hai đầu).
• rmq(lf, rg) --- Truy xuất thông tin: rương nào có ít vàng nhất trong đoạn từ \(lf\) đến \(rg\)?

Vì các rương được xếp thành vòng tròn, nên đoạn từ \(lf\) đến \(rg\) có thể được hiểu như sau:

• Nếu \(lf \le rg\): đoạn gồm các chỉ số từ \(lf\) đến \(rg\).
• Nếu \(lf > rg\): đoạn gồm các chỉ số từ \(lf\) đến \(n - 1\), rồi tiếp tục từ \(0\) đến \(rg\).

Hãy giúp Lập trình viên thực hiện tuần tự các thao tác, và ghi lại kết quả mỗi lần anh ta truy vấn rmq!

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) --- số lượng rương.
• Dòng thứ hai chứa \(n\) số nguyên \(a_0, a_1, \ldots, a_{n-1}\) \((-10^6 \le a_i \le 10^6)\) --- số lượng vàng ban đầu ở mỗi rương.
• Dòng thứ ba chứa số nguyên \(m\) \((0 \le m \le 2 \cdot 10^5)\) --- số truy vấn.

• \(m\) dòng tiếp theo, mỗi dòng chứa một truy vấn, có thể ở một trong hai dạng:

• lf rg --- Truy vấn loại rmq.

• lf rg v --- Truy vấn loại inc.

Output

Với mỗi truy vấn loại rmq, in ra một dòng chứa số lượng vàng ít nhất trong đoạn được hỏi.

Example

4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1

1
0
0