P1003 [NOIP 2011 上級組] カーペット敷設

問題文

特別な表彰式のために、主催者は会場の長方形の区域（直交座標系の第1象限とみなせる）に長方形のカーペットを敷きます。全部で \(n\) 枚のカーペットがあり、番号は \(1\) から \(n\) です。カーペットは番号の小さい順に、座標軸に平行に敷かれ、後から敷かれたカーペットは前のものを覆います。

すべて敷き終わった後、主催者はある座標点を覆う「最も上のカーペット」の番号を知りたいと考えています。注意：カーペットの境界や頂点上の点も覆われているとみなします。

入力形式

入力は \(n+2\) 行からなります。

最初の行には整数 \(n\) が与えられ、これはカーペットの総数を表します。

次の \(n\) 行にはカーペットの情報が与えられます。\((i+1)\) 行目には4つの整数 \(a, b, g, k\) が空白区切りで与えられ、カーペットの左下の座標 \((a, b)\) および \(x\) 軸方向と \(y\) 軸方向の長さを表します。

最後の行には2つの整数 \(x, y\) が与えられ、調べる点の座標 \((x, y)\) を表します。

出力形式

1 行に整数を1つ出力します。その点を覆うカーペットの番号を出力してください。もしどのカーペットにも覆われていない場合は -1 を出力してください。

入出力例 #1

入力 #1出力 #1

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

3

入出力例 #2

入力 #2出力 #2

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

-1

説明 / ヒント

入出力例 #1 の説明

次の図では、カーペット \(1\) は実線、カーペット \(2\) は破線、カーペット \(3\) は二重実線で表されています。点 \((2,2)\) を覆う最上位のカーペットは \(3\) です。

データ範囲

• \(30\%\) のデータでは、\(n \le 2\)。
• \(50\%\) のデータでは、\(0 \le a, b, g, k \le 100\)。
• \(100\%\) のデータでは、\(0 \le n \le 10^4\), \(0 \le a, b, g, k \le 10^5\).

NOIP 2011 上級組 Day \(1\), 問題 \(1\)。