Lật Hình Chữ Nhật · canuc80k4502

Mỗi test bắt đầu với một ma trận nhị phân $n \times n$ toàn số $0$ . Một lệnh có thể lật mọi bit trong một hình chữ nhật đóng; một lệnh khác hỏi bit hiện tại tại đúng một ô.

Input

Dòng đầu chứa số test $T$ .
Mỗi test bắt đầu bằng $n$ $q$ , sau đó là $q$ lệnh.
$C$ $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ lật hình chữ nhật; $Q$ $x$ $y$ hỏi một ô.

Output

In bit cho từng lệnh $Q$ . Sau phần kết quả của hai test liên tiếp có đúng một dòng trống.

Constraints

$1 \leq T \leq 10$ .
$2 \leq n \leq 1000, 1 \leq q \leq 5 \cdot 1 0^{4}$ .
$1 \leq x_{1} \leq x_{2} \leq n, 1 \leq y_{1} \leq y_{2} \leq n$ ; tọa độ truy vấn cũng nằm trong bảng.

Scoring

Subtask $1$ ( $50%$ số điểm): Trong mỗi test, $n, q \leq 100$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Ở test đầu, hình vuông $2 \times 2$ góc trên trái bị lật nên $(1, 1) = 1$ , còn $(3, 3) = 0$ . Ở test thứ hai, cột $2$ bị lật và ô $(2, 2)$ nhận giá trị $1$ .

Ý tưởng: Xem D là mảng hiệu 2D theo XOR. Muốn XOR 1 lên [x1..x2]×[y1..y2], XOR 1 tại bốn góc hiệu (x1,y1), (x1,y2+1), (x2+1,y1), (x2+1,y2+1). Giá trị thật tại (x,y) là XOR prefix của D tới (x,y). Dùng Fenwick 2D với phép gộp XOR thay cho cộng.
Chứng minh: Một góc hiệu bắt đầu hoặc kết thúc ảnh hưởng theo từng trục. Với một ô trong hình chữ nhật, đúng một tổ hợp góc còn hiệu lực nên nhận XOR 1; ngoài hình chữ nhật, số góc còn hiệu lực là chẵn nên triệt tiêu. Fenwick trả đúng XOR prefix của D, do đó query điểm đúng.
Độ phức tạp: Update hình chữ nhật và query điểm đều O(log²n); nhớ O(n²).
Lưu ý cài đặt: Cập nhật góc x2+1/y2+1 chỉ khi còn trong bảng; dùng cộng thay XOR; quên dòng trống giữa test.