Ctudor (silent 'C') just bought an $N$ by $N$ grid of cacti! He wants to monitor the happiness of each cactus. Cacti only have 2 moods - happy and sad. When Ctudor bought the cacti, all of them were happy. However, $Q$ events happen:

• 1 i j. The cactus at position $(i,j)$ suddenly switches their mood. If it was happy, it is now sad, and vice versa. It is common knowledge that a cactus's mood is easily affected by its surrounding cacti. Thus, when the cactus at position $(i,j)$ switches their mood, all the cacti that are on column $i$ or row $j$ switch their mood as well.
• 2 i j Ctudor would like to know the mood of the cactus at position $(i,j)$.

$1\le i,j\le N$.

Input Specification

The first line will contain two integers, $N,Q$ $(1\le N,Q\le {10}^5)$.

The next $Q$ lines will each contain an event as defined above.

Output Specification

For each type $2$ event, output 1 if the cactus at position $(i,j)$ is sad, and 0 if it is happy on its own line.

Constraints

Subtask 1 [10%]

$N,Q\le 100$

Subtask 2 [90%]

No additional constraints.

Sample Input

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

Sample Output

0
0
1