Problem: G: Code Art Online

Code Art Online (CAO) is an online RPG that advances adventures by solving various problems by programming. Since CAO was the world's first game that realized a virtual reality space, it was sold out while it was very popular, and users who purchased the game should enjoy this world. However, players who dive into the game are told a terrifying decree by the gamemaster.

"Unless some of you players solve the last problem of the last dungeon, you can't get out of this virtual space. And in this world, WA and TLE / RE mean death in the real world. I want you to start the problem with your heart. "

You are one of the CAO players, and you are doing your best to capture the game in order to clear this game and return to the real world. One day, you face the following problems.

This time, a party was formed with n members to capture the new dungeon. You are one of the parties. In order to enter the dungeon that you are about to capture, you must pass through a hole that can be seen from the cliff. If you can pass through the hole safely, you can enter the dungeon, but if you can not enter the hole and touch other parts, death is waiting. Furthermore, if someone passes through one hole, that hole will close, so each person must enter a separate hole.

Holes and people are considered on a two-dimensional plane. The shape of the hole is a circle of various sizes, as shown in Fig. G-1. In the input, the length of the radius is given.

<image>
---
Figure G-1: Hole shape

As shown in Fig. G-2, the human shape is given as a polygonal cross section of the human (not necessarily convex). In the input, the vertices are given counterclockwise to represent the shape of the polygon. It can be assumed that any three points of a polygon do not line up on a straight line. Furthermore, it is assumed that polygonal line segments do not intersect each other except for the purpose of forming vertices. It may rotate freely to pass through the hole (however, rotation in the z-axis direction is prohibited). It is assumed that the vertices of a polygon representing a person can pass through the hole even if it is on the circumference of the hole.

<image>
---
Figure G-2: Human shape

You, who have the highest algorithm skills in the party, decided to solve the decision problem of whether everyone can pass through the hole safely. If you can pass it safely, indicate who should pass which hole.

* You will not die in this contest, but if you make a mistake, please solve it with the intention of dying.

Input

On the first line, the integer n (1 <= n <= 100), which represents the number of holes, and the integer m (1 <= m <= n), which represents the number of parties, are entered separated by spaces.

In the next line, n integers ri (1 <= ri <= 1000) representing the radius of the hole are entered, separated by spaces. These holes are counted as the 1st hole, the 2nd hole, ..., and the nth hole in the order of input.

Then, information on the shape of m people is input. For the information of one person, the number of vertices p (3 <= p <= 100) of the polygon is first input to the first line. In the following line p, the coordinates of the vertices of the polygon are given counterclockwise. Integers xi, yi (-1000 <= xi, yi <= 1000) representing one vertex are entered in each line, separated by spaces. People are counted as the 1st person, the 2nd person, ..., and the mth person in the order of input.

Output

Output the number of hole that the person with i (1 <= i <= m) should enter. On the i-line, output the number of the hole that the person i should pass through.

If there are multiple paths, output the smallest path in lexicographical order. When there are two sequences A = {a1, a2, ..., am} and B = {b1, b2, ..., bm}, if A is smaller than B in lexicographical order, ai is bi. For the first i that is different, we say when ai is smaller than bi.

If no way is found, output one line as "NG". Don't forget to print a newline at the end.

Sample Input 1


3 3
25 100 10
8
-10 0
-twenty two
0 10
twenty two
10 0
twenty two
0 -10
-twenty two
Four
30 0
50 0
50 40
30 40
3
30 -10
45 -70
60 -10


Sample Output 1


3
1
2


Sample Input 2


4 3
25 15 15 30
Five
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


twenty two
1 30
Four
0 0
10 0
10 10
0 10
3
5 5
20 20
5 20


Sample Output 3


NG






Example

Input

3 3
25 100 10
8
-10 0
-2 2
0 10
2 2
10 0
2 -2
0 -10
-2 -2
4
30 0
50 0
50 40
30 40
3
30 -10
45 -70
60 -10


Output

3
1
2

Solution (in CPP):

Solution:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <utility>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define each(e,c) for(auto&e:c)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<" ["<<__LINE__<<"]"<<endl)
struct DUMP:ostringstream{template<class T>DUMP &operator,(const T&t){if(this->tellp())*this<<", ";*this<<t;return *this;}};
#else
#define dump(...)
#endif
template<class T> ostream& operator<<(ostream& os, vector<T> const& v){
    rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" ");
    return os;
}

#include <complex>
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define curr(g,i) g[i]
#define next(g,i) g[(i+1)%g.size()]
#define self (*this)

// 実数
typedef long double R;

// 実定数
const R eps = 1e-10;
const R inf = 1e12;
const R pi = acos(-1);

// 点
typedef complex<R> P;

// A->B->Cの順に廻るときの角ABCの大きさを[0,2*Pi]で求める
R arg(P a, P b, P c) { R th = arg((a - b) / (c - b)); return th > 0 ? th : th+2*pi; }

// 点のx座標優先の比較関数
bool comp_x(P const& a, P const& b) { return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b); }

// 点のy座標優先の比較関数
bool comp_y(P const& a, P const& b) { return imag(a) != imag(b) ? imag(a) < imag(b) : real(a) < real(b); }

// 点の偏角の比較関数
P CENTER = P();
bool comp_arg(P const& a, P const& b) { return arg(a, CENTER, CENTER+(R)1.) < arg(b, CENTER, CENTER+(R)1.); }

// 点のデフォルトの比較関数
namespace std { bool operator < (P const& a, P const& b) { return comp_x(a, b); } }

// 外積
R cross(P const& a, P const& b) { return imag(conj(a)*b); }

// 内積
R dot(P const& a, P const& b) { return real(conj(a)*b); }

// 直線
struct L : public vector<P> {
    L(P const& a = P(), P const& b = P()) { push_back(a); push_back(b); }
    L(R a, R b, R c){ // ax+by+c=0
        if(fabs(a) < eps) self = L(P(0,-c/b),P(1,-c/b));
        else if(fabs(b) < eps) self = L(P(-c/a,0),P(-c/a,1));
        else self = L(P(-c/a,0), P(0,-c/b));
    }
    P vec() const { return self[1] - self[0]; }
};

// 線分
struct S : public vector<P> {
    // A to B
    S(P const& a = P(), P const& b = P()) { push_back(a); push_back(b); }
    L line() const { return L(self[0], self[1]); }
    P vec() const { return line().vec(); }
    R len() const { return abs(vec()); }
};

// 多角形
typedef vector<P> G;

// 円
struct C {
    P p; R r;
    C(P const& p = P(), R r = 0) : p(p), r(r) { }
};

// A->B->C と巡るときの位置関係を調べる
enum { CCW = +1, CW = -1, CAB = +2, ABC = -2, SEG = 0 };
int ccw(P a, P b, P c) {
    b -= a; c -= a;
    if (cross(b, c) > 0)   return CCW; // a->b->c 反時計回り
    if (cross(b, c) < 0)   return  CW; // a->b->c 時計回り
    if (dot(b, c) < 0)     return CAB; // c--a--b 直線上
    if (norm(b) < norm(c)) return ABC; // a--b--c 直線上
    return SEG; // 線分上にある
}

// 円の面積
R area(C const& c) { return pi*c.r*c.r; }

// 多角形の面積
R area(G const& g) { R res = 0; int n = g.size(); rep(i,n) res += cross(g[i],g[(i+1)%n]); return abs(res)/2; }

// ヘロンの公式
R heron(R a, R b, R c) { R s = (a+b+c)/2; return sqrt(s*(s-a)*(s-b)*(s-c)); }

P biased_center(P const& a, P const& b, P const& c, R wa, R wb, R wc) {
    return (wa*a + wb*b + wc*c)/(wa + wb + wc);
}

// http://www.h6.dion.ne.jp/~ooya/Suugaku/IchiVector5shin.pdf
// 重心
P gravity_center(P const& a, P const& b, P const& c) {
    return biased_center(a,b,c,1,1,1);
}

// 内心
P inner_center(P const& a, P const& b, P const& c) {
    R la = abs(b-c), lb = abs(c-a), lc = abs(a-b);
    return biased_center(a,b,c,la,lb,lc);
}

// 外心
P circumcenter(P const& a, P const& b, P const& c) {
    R sa = sin(2*arg(c,a,b)), sb = sin(2*arg(a,b,c)), sc = sin(2*arg(b,c,a));
    return biased_center(a,b,c,sa,sb,sc);
}

// 垂心
P orthocenter(P const& a, P const& b, P const& c) {
    if(abs(arg(c,a,b))==pi) return a;
    if(abs(arg(a,b,c))==pi) return b;
    if(abs(arg(b,c,a))==pi) return c;
    R ta = tan(arg(c,a,b)), tb = tan(arg(a,b,c)), tc = tan(arg(b,c,a));
    return biased_center(a,b,c,ta,tb,tc);
}

// 傍心(3つのうち頂点Aに対応するものを返す)
P excenter(P const& a, P const& b, P const& c) {
    R sa = sin(arg(c,a,b)), sb = sin(arg(a,b,c)), sc = sin(arg(b,c,a));
    return biased_center(a,b,c,-sa,sb,sc);
}

// 直線と直線の交差判定
bool col(L const& l, L const& m) { return abs(cross(l.vec(), m.vec())) > eps || abs(cross(l.vec(), m[0]-l[0])) < eps; }

// 直線と線分の交差判定
bool col(L const& l, S const& s) { return cross(l.vec(), s[0]-l[0])*cross(l.vec(), s[1]-l[0]) < eps; }
bool col(S const& s, L const& l) { return col(l, s); }

// 直線と点の交差判定
bool col(L const& l, P const& p) { return abs(cross(l[1]-p, l[0]-p)) < eps; }
bool col(P const& p, L const& l) { return col(l, p); }

// 線分と線分の交差判定
bool col(const S &s, const S &t) { return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 && ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0; }

// 線分と点の交差判定
bool col(const S &s, const P &p) { return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < eps; }

// 円と円の交差判定
int col(const C& c1, const C& c2){
    R d = abs(c1.p - c2.p), r1 = c1.r, r2 = c2.r;
    if(r1 + r2 < d)                 return 0; // 離れている
    if(abs(r1 + r2 - d) < eps)      return 1; // 外接
    if(abs(d - abs(r1 - r2)) < eps) return -1; // 内接
    if(d < r1 - r2)                 return +3; // c1 が c2 の中にある
    if(d < r2 - r1)                 return -3; // c2 が c1 の中にある
    return 2; // 2つの交点を持つ
}

// 点の射影
P proj(L const& l, P const& p) { R t = dot(p-l[0], l.vec()) / norm(l.vec()); return l[0] + t*(l.vec()); }
P proj(P const& p, L const& l) { return proj(l, p); }

// 点の反射
P refl(L const& l, P const& p) { return p + (R)2 * (proj(l, p) - p); }
P refl(P const& p, L const& l) { return refl(l, p); }

// 点と点の距離
R dist(P const& p, P const& q) { return abs(p - q); }

// 点と直線の距離
R dist(L const& l, P const& p) { return abs(p - proj(l, p)); }
R dist(P const& p, L const& l) { return dist(l, p); }

// 直線と直線の距離
R dist(L const& l, L const& m) { return col(l, m) ? 0 : dist(l, m[0]); }

// 直線と線分の距離
R dist(L const& l, S const& s) { return col(l, s) ? 0 : min(dist(l, s[0]), dist(l, s[1])); }
R dist(S const& s, L const& l) { return dist(l, s); }

// 線分と点の距離
R dist(S const& s, P const& p) { P const r = proj(s.line(), p); return col(s, r) ? abs(r - p) : min(abs(s[0] - p), abs(s[1] - p)); }
R dist(P const& p, S const& s) { return dist(s,p); }

// 線分と線分の距離
R dist(S const& s, S const& t) { return col(s, t) ? 0 : min(min(min(dist(s, t[0]), dist(s, t[1])), dist(t, s[0])), dist(t, s[1])); }

// 直線と直線の交点
vector<P> hit(L const& l, L const& m) {
    R A = cross(l.vec(), m.vec());
    R B = cross(l.vec(), l[1] - m[0]);
    if (abs(A) < eps && abs(B) < eps) return {m[0]}; // same line
    if (abs(A) < eps) return G(); // parallel
    return {m[0] + B / A * (m.vec())};
}

// 線分と線分の交点
vector<P> hit(S const& s, S const& t) { return col(s,t) ? hit(s.line(),t.line()) : G(); }

// 直線と線分の交点
vector<P> hit(L const& l, S const& s) { return col(l, s) ? hit(l, s.line()) : G(); }
vector<P> hit(S const& s, L const& l) { return hit(l, s); }

// Verify : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1183
//        : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2045
// 円と直線の交点を求める
vector<P> hit(C const& c, L const& l){
    R d = dist(l,c.p); // 中心と直線の距離
    if(fabs(d-c.r) < eps) return { proj(l, c.p) }; // 触れている
    if(d > c.r) return G(); // 離れている
    P h = proj(l, c.p);
    P u = sqrt(c.r*c.r - d*d) * (l.vec()) / abs(l.vec());
    return {h+u, h-u};
}

// 円と線分の交点を求める
vector<P> hit(C const& c, S const& s) { G cps = hit(c,s.line()), res; for(const P& p : cps) if(col(s,p)) res.push_back(p); return res; }

// 円と円の交点を求める
vector<P> hit(C const& c1, C const& c2) {
    if(abs(c1.p - c2.p) < 0) return G(); // 中心が同じ
    int i = col(c1,c2);
    if(i==0 || abs(i)==3) return G(); // 共通部分なし || 内部
    R r1 = c1.r, r2 = c2.r, d = abs(c1.p - c2.p);
    if(i==1) return { c1.p + (c2.p - c1.p) * r1/d }; // 接する
    P p = c1.p - c2.p;
    R A = -2. * p.real(), B = 2 * p.imag();
    R C = norm(c1.p) - norm(c2.p) - r1*r1 + r2*r2;
    return hit(c1, L(A,B,C)); // 2つの交点を持つ
}

// 円と多角形の交点を求める
vector<P> hit(C const& c, G const& g) {
    vector<P> res; int n = g.size();
    rep(i,n) for(P const& p : hit(c, S(g[i],g[(i+1)%n]))) res.push_back(p);
    return res;
}

// !!! not verified !!!
C min_ball(G const& g){
    int n = g.size();
    if(n==1) return C(g[0],0);
    if(n==2) return C((g[0]+g[1])/(R)2, abs((g[0]+g[1])/(R)2-g[0]));
    P c = (g[0]+g[n/3]+g[n/3*2])/(R)3;
    R r = 1.0;
    rep(i,100){
        R d = 0;
        int x = 0;
        rep(j,n){
            if(d < norm(g[j]-c)){
                d = norm(g[j]-c);
                x = j;
            }
        }
        c += (g[x]-c)*r;
        if(i&2) r *= 0.8;
    }
    R d = 0;
    int x = 0;
    rep(i,n){
        if(d < norm(c-g[i]) + eps){
            d = norm(c-g[i]); x = i;
        }
    }
    return C(c,abs(c-g[x]));
}

int n,m;
R r[111], mb[111];

vi ans;
bool used[111];

bool chk(int s){
    vi b;
    rep(i,n)if(!used[i]) b.eb(r[i]);
    vector<R> a;
    loop(i,s,m) a.eb(mb[i]);
    sort(all(a));
    sort(all(b));
    int last = -1;
    rep(i,a.size()){
        bool found = false;
        loop(j,last+1,b.size()){
            if(a[i] < b[j] + eps){
                found = true;
                last = j;
                break;
            }
        }
        if(!found)return false;
    }
    return true;
}

int main(){
#ifdef LOCAL
    freopen("in","r",stdin);
#endif
    while(cin >> n >> m){
        ans.clear();
        rep(i,n) cin >> r[i];
        rep(i,m){
            int k; cin >> k;
            G g(k);
            rep(j,k){
                R x,y;
                cin >> x >> y;
                g[j] = P(x,y);
            }
            mb[i] = min_ball(g).r;
        }

        rep(i,m) used[i] = false;
        bool f = true;
        rep(i,m){
            bool found = false;
            rep(j,n){
                if(used[j]) continue;
                if(!(mb[i] < r[j] + eps)) continue;
                used[j] = true;
                if(chk(i+1)){
                    ans.push_back(j);
                    found = true;
                    break;
                }
                used[j] = false;
            }
            if(!found){
                f = false; break;
            }
        }
        if(f){
            rep(i,m) cout << ans[i]+1 << "\n";
        }
        else cout << "NG" << endl;
    }
}