009 - 線分配置

Ａ大学は今年もプログラミングコンテストを開催する。作題チームの一員であるあなたは、計算幾何学の問題の入力データの作成を担当することになった。あなたが作りたい入力データは、x 軸または y 軸に平行で、互いに触れ合うことのない線分の集合である。あなたは、次のアルゴリズムに基づいたデータ生成プログラムを開発して、入力データを生成する。

1. xy 平面上の線分の集合 T を空にする。
2. 次の処理を N 回繰り返す。
   • x 軸または y 軸に平行な適当な線分 s を作る。
   • s が T 内のどの線分にも触れない場合は s を T に追加し、触れる場合は s を追加しない。

x 軸または y 軸に平行な N 本の線分を順番に入力し、各線分が平面上に追加されるかどうかを判定するプログラムを作成せよ。

input

入力は以下の形式で与えられる。

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

１行目に線分の数 N (1 ≤ N ≤ 100000) が与えられる。続く N 行に、i 番目に追加したい線分の情報が与えられる。各行に与えられる４つの整数 px_i, py_i, qx_i, qy_i (0 ≤ px_i, py_i, qx_i, qy_i ≤ 10⁹) は、それぞれ i 番目の線分の端点の x 座標、y 座標、もう一つの端点の x 座標、y 座標を表す。ただし、線分の長さは１以上である。

出力

各線分について、追加される場合「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
1
0
1
0
1
1
0
1