牛はパズルが大好きだということはあまり知られていません！Bessie の誕生日に、Farmer John は面白い機械パズルを贈りました。三つの固体からなり、それぞれ $1\times1$ の単位正方形を貼り合わせています。各形は「連結」で、どの正方形からも物体の正方形を通って北・南・東・西へ進むことで他のどの正方形にも到達できます。

各物体を北・南・東・西に 1 単位ずつ繰り返し滑らせて動かします。目標は、それぞれの境界ボックスが互いに交わらないよう分離することです。三つの形と位置から、分離できるか Bessie を手伝って判断してください。分離できない配置はロック状態と呼びます。

[注：出力をランダムに推測するだけのプログラムは失格となり、0 点になる場合があります。]

入力

• 行 1：空白区切りの 3 整数 $N1$、$N2$、$N3$、それぞれ物体 1、2、3 の単位正方形数です。
• 行 $2\ldots1+N1$：各行は物体 1 の正方形 1 個の南西角の座標 $(x,y)$ を示します。全座標は範囲 $0\ldots9$ にあります。
• 行 $2+N1\ldots1+N1+N2$：各行は物体 2 の正方形 1 個の南西角の座標 $(x,y)$ を示します。全座標は範囲 $0\ldots9$ にあります。
• 行 $2+N1+N2\ldots1+N1+N2+N3$：各行は物体 3 の正方形 1 個の南西角の座標 $(x,y)$ を示します。全座標は範囲 $0\ldots9$ にあります。

出力

• 行 1：互いに分離できるなら 1、ロック状態なら 0 を出力します。

入出力例

入力 1

12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2

出力 1

1

注記

物体 1 は 12 個、物体 2 は 3 個、物体 3 は 5 個の正方形からなります。形は上の図の通りです。

問題作成：Brian Dean, 2012