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 jCtudor would like to know the mood of the cacti at position ~(i, j)~.
~1 \le i, j \le N~.
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.
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.
Subtask 1 [10%]
~N, Q \le 100~
Subtask 2 [90%]
No additional constraints.
4 5 2 2 2 1 3 3 1 2 2 2 3 2 2 3 3
0 0 1