Description

Translated from [CERC2018] Shooter Island.

You have recently been promoted to captain, and now you are leading your soldiers on a special mission in a blizzard. The battlefield is quite unusual because it is located on a giant ice sheet within the Arctic Circle. You need to coordinate with headquarters. Headquarters has many powerful computers to help you obtain the latest state of the battlefield. The AI interface models the battlefield as a grid. Each cell is uniquely identified by its row and column indices. Larger rectangles formed by cells are described by the pair of cells at their opposite corners. Initially, all cells are covered by ice.

You can receive two types of information from the computer:

1. Strike information ($t=0$): the enemy strikes the rectangular area described by cells $[x_1,y_1]$ and $[x_2,y_2]$, and then this rectangular area is flooded by the cold Arctic Ocean water.
2. Queries from your soldiers ($t=1$): they ask whether it is possible to travel by boat from $[x_1,y_1]$ to $[x_2,y_2]$. The boat can be represented as a circle with radius $0.31416$. Note that the entire hull must always stay afloat on water, and it cannot leave the battlefield area.

Your soldiers need your help. Can you guide them reliably to complete the mission?

Input Format

The first line contains an integer $L$, the number of following lines.

The next $L$ lines each contain five integers $t,x_1,y_1,x_2,y_2$, where $t$ is the type of information, and $[x_1,y_1]$, $[x_2,y_2]$ denote the corresponding cells.

Output Format

For each query, output $1$ if it is possible to travel by boat from $[x_1,y_1]$ to $[x_2,y_2]$, otherwise output $0$.

6
0 4 4 6 6
0 6 6 7 8
0 1 3 3 3
1 1 7 6 1
1 5 4 6 8
1 4 5 1 3

0
1
0

3
0 1 1 1 1
0 1 2 1 2
1 1 1 1 2

1

Hint

Sample Input 1 is shown in the figure below:

Constraints: $1 \leq L \leq 2 \times 10^5, t \in \{0, 1\}, 1 \leq x_1, x_2 \leq 50, 1 \leq y_1, y_2 \leq 10^5$.

Translated by ChatGPT 5