Shooter Island

Time limit3sMemory limit512 MB

Summary

On a 50 by 100000 grid, rectangles flood when hit, and after each query decide whether a radius-0.31416 boat can sail between two given squares on the remaining water.

Level: Hard8 of 10
Topics: Union-find, Intervals, Geometry, Implementation
Solved: No attempts yet

Problem

You were recently promoted to captain, and your troopers are now on a special mission in a storm. The battlefield is unusual: it lies above the Arctic Circle on a huge ice floe. You direct the operation from headquarters. Many high-end computers keep you informed of events on the battlefield, which the AI interface models as a grid of unit squares. Each unit square is identified by its row and column index in the grid. Larger rectangles made of unit squares are given by a pair of unit squares at opposite corners of the rectangle. At the start, every square is covered with ice.

You receive two kinds of information from the computers:

Hit reports: the enemy has hit the rectangle given by the unit squares [x1,y1] and [x2,y2]. That rectangle is immediately flooded with cold Arctic water.
Queries from your troopers: they ask whether a boat can travel from square [x1,y1] to square [x2,y2]. The boat is represented by a circle of radius 0.31416. The boat must stay entirely on the water surface at all times, and it may not leave the battlefield area.

Your troopers need your help. Can you guide them reliably?

Input

The first line contains an integer L (1 ≤ L ≤ 2 · 105), the number of lines that follow. Each of the next L lines contains five integers t, x1, y1, x2, y2 (t ∈ {0, 1}, 1 ≤ x1, x2 ≤ 50, 1 ≤ y1, y2 ≤ 105). The number t is the type of information, and the pairs [x1, y1] and [x2, y2] specify the respective unit squares.

Output

For each query, print 1 if a boat can travel from unit square [x1,y1] to unit square [x2,y2], and 0 otherwise.

Examples2

Example 1

Input

Expected output

0
1
0

Example 2
Input
```
3
0 1 1 1 1
0 1 2 1 2
1 1 1 1 2
```
Expected output
```
1
```