Valentine's Day '19 S2 - Ctudor's Cute Cacti

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

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.


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



There are no comments at the moment.