Code Art Online

G: コードアートオンライン

コードアートオンライン（CAO）は，様々な問題をプログラミングによって解くことにより，冒険を進めて行くオンラインRPGである． CAOは，世界初のバーチャルリアリティ空間を実現したゲームであったこともあり，大人気の内に完売し，ゲームを購入したユーザ達はこの世界を楽しむはずであった．しかし，ゲームにダイブしたプレイヤー達は，ゲームマスターから恐るべき託宣を聞かされる．

「君たちプレイヤーの内の誰かが，ラストダンジョンのラストプロブレムを解かない限り，この仮想空間から抜け出すことはできない．そして，この世界での，WAやTLE・REは，現実世界での死を意味する．心して問題にとりかかってほしい．」

あなたも，CAOのプレイヤーの内の1人で，このゲームをクリアして現実世界に戻るために，ゲーム攻略に全力を尽くしている．ある日，あなたは次のような問題に直面することとなった．

今回，新たなダンジョンを攻略するために，n人のメンバーでパーティが組まれた．あなたもこのパーティの内の1人である．今から攻略するダンジョンに突入するためには，崖から見える穴を通過しなくてはならない．無事に穴を通過できれば，ダンジョンに突入できるが，穴に突入できず他の部分に触れてしまうと，死が待っている．さらに，1つの穴に誰かが通ると，その穴は閉じてしまうため，1人1人別々の穴に入らなければならない．

穴や人は，二次元平面上で考えることとする．穴の形は，図G-1のような，大小様々な円である．入力では，半径の長さが与えられる．

図G-1: 穴の形

人の形は，図G-2のように人の断面が多角形で与えられる（凸とは限らない）．入力では，多角形の形を表すために，頂点が反時計まわりで与えられる．多角形の任意の三点は，1直線上に並ばないと仮定してよい．さらに，頂点を構成する目的以外で，多角形の線分同士が交差することはないものとする．穴に通すために，自由に回転してよい（ただし，z軸方向への回転は禁止する）．人を表す多角形の頂点が，穴の円周上にある場合でも，穴を通過できるものとする．

図G-2: 人の形

パーティの中で最もアルゴリズムスキルが高いあなたは，みんなで無事に穴を通過できるかどうかの判定問題を解くことにした．もし，無事に通過できるなら，どの人がどの穴を通過すればいいのか表示せよ．

※今回のコンテストで死ぬことはありませんが，間違ったら死ぬつもりで解いてください．

Input

1行目に，穴の数を表す整数n (1 <= n <= 100)と，パーティの人数を表す整数m (1 <= m <= n)がスペース区切りで入力される．

次の行に，穴の半径を表す整数r_i (1 <= r_i <= 1000)がスペース区切りでn個入力される．これらの穴は，入力された順番に，1番の穴, 2番の穴, ..., n番の穴と数えることとする．

続いて，m人の人の形の情報が入力される． 1人の情報は，まず1行目に多角形の頂点数p (3 <= p <= 100)が入力される．続くp行には，多角形の頂点の座標が反時計周りで与えられる．各行には，1つの頂点を表す整数x_i, y_i (-1000 <= x_i, y_i <= 1000)がスペース区切りで入力される．人は，入力された順番に，1番の人, 2番の人, ..., m番の人と数えることとする．

Output

i番(1 <= i <= m)の人が，何番の穴に入ればいいかを出力せよ． i行目には，i番の人が通るべき穴の番号を出力すること．

もし，複数の通り方がある場合，辞書順で一番小さくなる通り方を出力すること． 2つの数列A = {a₁, a₂, ..., a_m}とB = {b₁, b₂, ..., b_m}があったとき，AがBより辞書順で小さいとは，a_iがb_iと異なるような最初のiについて，a_iがb_iより小さいときのことを言う．

通り方が1つも見つからない場合は，"NG"と1行出力すること．最後に改行を出力するのを忘れないこと．

Sample Input 1

Sample Output 1

3
1
2

Sample Input 2

4 3
25 15 15 30
5
0 0
10 0
20 10
0 20
-20 10
3
20 0
40 0
30 10
3
-50 0
-30 0
-40 10

Sample Output 2

1
2
3

Sample Input 3

Sample Output 3

NG

Note

Commentary

Source: https://onlinejudge.u-aizu.ac.jp/problems/2423