Line Segment Arrangement

University A will hold a programming contest this year as well. As a member of the writing team, you will be responsible for creating the input data for computational geometry problems. The input data you want to create is a set of line segments that are parallel to the x-axis or y-axis and do not touch each other. You develop a data generation program based on the following algorithm to generate input data.

1. Empty the set T of line segments on the xy plane.
2. Repeat the following process N times.

• Make a suitable line segment s parallel to the x-axis or y-axis.
• Add s to T if s does not touch any line segment in T, do not add s if it does.

Write a program that inputs N line segments parallel to the x-axis or y-axis in order and determines whether each line segment is added on the plane.

Input

The input is given in the following format.

N px1 py1 qx1 qy1 px2 py2 qx2 qy2 :: pxN pyN qxN qyN

The number of line segments N (1 ≤ N ≤ 100000) is given in the first line. The following N lines are given the information of the line segment that you want to add to the i-th. The four integers pxi, pyi, qxi, qyi (0 ≤ pxi, pyi, qxi, qyi ≤ 109) given in each line are the x-coordinate, y-coordinate, and x of the other end point, respectively. Represents coordinates and y coordinates. However, the length of the line segment is 1 or more.

Output

For each line segment, "1" is output when added, and "0" is output on one line when not added.

Example

Input

9 0 2 5 2 1 3 1 7 0 6 3 6 2 4 8 4 4 0 4 5 6 3 6 0 5 6 7 6 8 3 8 7 6 5 11 5

Output

1 1 0 1 0 1 1 0 1

inputFormat

input data for computational geometry problems. The input data you want to create is a set of line segments that are parallel to the x-axis or y-axis and do not touch each other. You develop a data generation program based on the following algorithm to generate input data.

1. Empty the set T of line segments on the xy plane.
2. Repeat the following process N times.

• Make a suitable line segment s parallel to the x-axis or y-axis.
• Add s to T if s does not touch any line segment in T, do not add s if it does.

Write a program that inputs N line segments parallel to the x-axis or y-axis in order and determines whether each line segment is added on the plane.

Input

The input is given in the following format.

N px1 py1 qx1 qy1 px2 py2 qx2 qy2 :: pxN pyN qxN qyN

The number of line segments N (1 ≤ N ≤ 100000) is given in the first line. The following N lines are given the information of the line segment that you want to add to the i-th. The four integers pxi, pyi, qxi, qyi (0 ≤ pxi, pyi, qxi, qyi ≤ 109) given in each line are the x-coordinate, y-coordinate, and x of the other end point, respectively. Represents coordinates and y coordinates. However, the length of the line segment is 1 or more.

outputFormat

Output

For each line segment, "1" is output when added, and "0" is output on one line when not added.

Example

Input

9 0 2 5 2 1 3 1 7 0 6 3 6 2 4 8 4 4 0 4 5 6 3 6 0 5 6 7 6 8 3 8 7 6 5 11 5

Output

1 1 0 1 0 1 1 0 1

样例

9
0 2 5 2
1 3 1 7
0 6 3 6
2 4 8 4
4 0 4 5
6 3 6 0
5 6 7 6
8 3 8 7
6 5 11 5

1
1
0
1
0
1
1
0
1

</p>