Shooter Island Navigation

You are the newly promoted captain leading your soldiers on a special mission through a fierce blizzard on a giant Arctic ice sheet. The battlefield is modeled as an n × m grid, where each cell is uniquely identified by its row and column indices. Initially, every cell is covered by ice.

The headquarters sends you information through two types of messages:

1. Strike update (t = 0): The enemy has attacked a rectangular region of the grid. The region is specified by two opposite corner cells \( [x_1,y_1] \) and \( [x_2,y_2] \). Immediately after the strike, all cells in this rectangle become flooded with the freezing waters of the North Atlantic.
2. Sailing query (t = 1): Your soldiers ask whether it is possible to sail from cell \( [x_1,y_1] \) to cell \( [x_2,y_2] \) by boat. The boat is modeled as a circle with radius \( r = 0.31416 \) (in units where each cell has side length 1). Throughout the journey, the entire boat (i.e. the entire circle) must remain on water and inside the battlefield.

For a boat to sail between two cells, there must exist a continuous path within the water such that the boat – while maintaining a clearance of at least \( r=0.31416 \) from any ice (or the battlefield boundary) – can travel from the starting cell to the destination cell. In our setting, if two water cells share a side, then they are considered connected (the clearance is sufficient as \( 0.31416 < 0.5 \)).

You are to process a series of commands and for each sailing query decide whether a safe route exists.

Note: For the purposes of this problem, you may assume that boat connectivity is equivalent to 4-direction connectivity among flooded (water) cells.

inputFormat

The first line contains three integers n, m and q (1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 100000), representing the number of rows, columns, and the number of operations, respectively.

Each of the following q lines contains five integers: t, x₁, y₁, x₂, y₂. If t = 0, then the rectangle defined by the two opposite corners \( [x_1,y_1] \) and \( [x_2,y_2] \) is struck and all cells in it become water. If t = 1, then this line is a query asking whether it is possible to sail from cell \( [x_1,y_1] \) to cell \( [x_2,y_2] \) under the condition described above.

It is guaranteed that the coordinates satisfy 1 ≤ x_i ≤ n and 1 ≤ y_i ≤ m. Note that the two corner cells may be given in any order; use the minimal and maximal coordinates to define the rectangle.

outputFormat

For each query (t = 1) in the input, output a single line containing 1 if it is possible to sail from the starting cell to the destination cell, or 0 otherwise.

sample

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

1
0
1