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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.


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



There are no comments at the moment.