Problem K
Keep Them Separated

Team Socket was defeated by Bash — the Pokenom trainer — and Bash’s best Pokenom Chikapu for the $10^9 + 7$-th time. Team Socket realized that Bash and Chikapu were simply too strong together. Now team Socket is devising an evil plan to keep Bash and Chikapu separated! Team Socket has built an evil machine, which can instantly build a rectangular wall or instantly remove a rectangular wall.

Given the locations where Team Socket is going to build and remove walls, can you help Team Socket check whether Bash and Chikapu are separated?

You are given $Q$ queries, numbered from $1$ to $Q$. The $i$-th query can be one of the following $3$ types:

  • $1 \, x_1 \, y_1 \, x_2 \, y_2$: Team Socket builds a rectangular wall, with sides parallel to the axes, and $2$ opposite corners at $(x_1, y_1)$ and $(x_2, y_2)$ $(x_1 \ne x_2, y_1 \ne y_2)$.

  • $2 \, j$: Team Socket removes the rectangular wall built in the $j$-th query. It is guaranteed that $j$-th query is of the $1$st type, the wall was built before this query (i.e. $j < i$), and the wall was not removed previously.

  • $3 \, x_1 \, y_1 \, x_2 \, y_2$: Bash is standing at $(x_1, y_1)$, and Chikapu is standing at $(x_2, y_2)$. Please let Team Socket know if there is a path from Bash to Chikapu. Of course, both Bash and Chikapu cannot walk through any walls.


The first line of input contains exactly one integer $Q$ — the number of queries $(1 \le Q \le 10^5)$.

Then $Q$ lines follow, the $i$-th line is one of 3 types:

  • $1 \, x_1 \, y_1 \, x_2 \, y_2$

  • $2 \, j$

  • $3 \, x_1 \, y_1 \, x_2 \, y_2$

All coordinates in the input file are integers from $1$ to $5\, 000$, inclusive. It is guaranteed that:

  • After each query, no 2 walls have a common point.

  • In all queries of 1st type, $x_1, y_1, x_2, y_2$ are odd numbers.

  • In all queries of 3rd type, $x_1, y_1, x_2, y_2$ are even numbers.


For each query of third type, print a character ‘Y’ if there is a path from Bash to Chikapu. Otherwise, print a character ‘N’. Please note that this problem uses case-sensitive checker.

Sample clarification

\includegraphics[width=0.9\textwidth ]{example59.png}
Sample Input 1 Sample Output 1
3 2 2 8 8
1 1 1 7 7
3 2 2 8 8
3 2 2 6 6
1 3 3 5 5
3 4 4 8 8
2 2
3 2 2 8 8
3 4 4 8 8
CPU Time limit 1 second
Memory limit 1024 MB
Source The 2018 ICPC Vietnam National Programming Contest
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in