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 cacti 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.

Subtasks

Subtask 1 [10%]

~N, Q \le 100~

Subtask 2 [90%]

No further 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