Description

The pirates’ cave is an $n \times n$ grid, and each cell can store a lot of treasure. All cells are initially empty. The pirate leader decides to hide these treasures in some rectangular regions, and also to learn the parity of the number of treasures in some rectangular regions. However, there is so much treasure that he gets dizzy organizing it, so he asks you for help.

Input Format

The first line contains two positive integers n and m, representing the grid size and the number of operations.

Each of the following m lines is one of two operations:

1. P x1 y1 x2 y2 k a1 b1 a2 b2 … ak bk: add b1 items of type a1, b2 items of type a2, …, bk items of type ak to every cell in the rectangular region from (x1, y1) to (x2, y2) inclusive. Here, k is the number of (ai, bi) pairs listed.

2. Q x1 y1 x2 y2: query the parity of the total number of items of each type within the rectangular region from (x1, y1) to (x2, y2) inclusive.

Output Format

For each Q operation, output one line containing a string of length 30 composed of ‘1’ and ‘2’. If the count of the k-th item type is even, then the k-th character from left to right is ‘1’; otherwise it is ‘2’. There are no spaces between characters.

(Note: even -> 1, odd -> 2.)

5 5
P 1 1 5 5 3 1 1 2 1 3 1
Q 1 1 5 5
Q 1 1 4 3
P 1 1 5 5 3 1 2 2 1 3 2
Q 1 2 3 4

222111111111111111111111111111
111111111111111111111111111111
212111111111111111111111111111

Hint

• 30% of the testdata: $n \le 300$, $m \le 300$.
• Constraints for 100% of the testdata: $n \le 2500$, $m \le 50000$, $1 \le x1 \le x2 \le n$, $1 \le y1 \le y2 \le n$, $1 \le a_i \le 30$, $1 \le b_i \le 100$.

Translated by ChatGPT 5