#include<iostream>
#include<cstdio>
#include<cfloat>
#include<cassert>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

#define REP(i, b, e) for ( int i = b; i < e; i++ )
#define rep(i,n) REP(i, 0, n)

#define EPS (1e-8)
#define equals(a, b) (fabs((a) - (b)) < EPS )
#define dle(a, b) (equals(a, b) || a < b )

class Point{
    public:
    double x, y;
     int id;
  Point ( double x = 0, double y = 0, int id = 0): x(x), y(y), id(id){}

    Point operator + ( Point p ){ return Point(x + p.x, y + p.y); }
    Point operator - ( Point p ){ return Point(x - p.x, y - p.y); }
    Point operator * ( double a ){ return Point(x*a, y*a); }
    Point operator / ( double a ){ return Point(x/a, y/a); }

    double abs() { return sqrt(norm());}
    double norm() { return x*x + y*y; }

    bool operator < ( const Point &p ) const {
	return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == ( const Point &p ) const {
	return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
    }
};

typedef Point Vector;

class Segment{
    public:
    Point p1, p2;
    Segment(Point s = Point(), Point t = Point()): p1(s), p2(t){}
};

typedef vector<Point> Polygon;

double norm( Vector a ){ return a.x*a.x + a.y*a.y; }
double abs( Vector a ){ return sqrt(norm(a)); }
Point polar( double a, double r ){ return Point(cos(r)*a, sin(r)*a);}
double getDistance( Vector a, Vector b ){ return abs(a - b); }
double dot( Vector a, Vector b ){ return a.x*b.x + a.y*b.y; }
double cross( Vector a, Vector b ){ return a.x*b.y - a.y*b.x; }

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw( Point p0, Point p1, Point p2 ){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if ( cross(a, b) > EPS ) return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS ) return CLOCKWISE;
    if ( dot(a, b) < -EPS ) return ONLINE_BACK;
    if ( norm(a) < norm(b) ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

double arg(Vector p){
    return atan2(p.y, p.x);
}

bool yxCmp( const Point &p1, const Point &p2 ) {
    return (p1.y == p2.y) ? p1.x < p2.x : p1.y < p2.y;
}

class PolarAngleCmp{
    public:
    Point o;
    PolarAngleCmp( Point o): o(o){}
    bool operator()( const Point &p1,  const Point &p2) const {
	Vector a = Vector(p1.x-o.x, p1.y-o.y); // p1 - o
	Vector b = Vector(p2.x-o.x, p2.y-o.y); // p2 - o
	double c = cross(a, b);
	if ( fabs(c) < EPS ) return abs(a) < abs(b);
	return c > 0;
    }
};

double getArea(Point p1, Point p2, Point p3){
    return abs(0.5 * ((p3.y-p1.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p3.x-p1.x)));
}

double getArea(Polygon p){
    double sum = 0.0;
    for(int i = 0; i < p.size(); i++){
	sum += cross(p[i], p[(i+1)%p.size()]);
    }
    return abs(sum/2);
}

class State{
public:
  int j, l, k;
  State(){}
  State(int j, int l, int k): j(j), l(l), k(k){}
};

static const int MAX = 41;
static const int INF = (1<<30);

int N, K;
vector<Point> P;
bool used[MAX];

double mina[MAX];
vector<int> ans[MAX];

vector<vector<int> > V[MAX];
  Polygon IN;

/*
 dp i, j, k
 */
void solve(vector<Point> C){
  int n = C.size();
  if ( n < 3 ) return;
  assert( C.begin() == min_element(C.begin(), C.end(), yxCmp));
  Point lm = *min_element(C.begin(), C.end(), yxCmp);
  sort(C.begin(), C.end(), PolarAngleCmp(lm));
  double dp[MAX][MAX][MAX];
  State pi[MAX][MAX][MAX];

  rep(i, n) rep(j, n) rep(k, n+1) {
    dp[i][j][k] = INF;
    pi[i][j][k] = State(-1, -1, -1);
  }

  for ( int j = 2; j < n; j++ ){
    for ( int l = j-1; l >= 1; l-- ){
      dp[j][l][3] = getArea(C[0], C[j], C[l]);

      vector<int> a;
      a.push_back(C[j].id);
      a.push_back(C[l].id);
      a.push_back(C[0].id);

      //      V[3].push_back(a);
      if ( mina[3] > dp[j][l][3] ){
	mina[3] = dp[j][l][3];
	ans[3] = a;
      }
    }
  }

  for ( int m = 4; m <= n; m++ ){
    for ( int j = 2; j < n; j++ ){ // last point
      for ( int l = j-1; l >= 1; l-- ) {
	for ( int k = l-1; k >= 0; k-- ){
	  if ( ccw(C[k], C[l], C[j]) == CLOCKWISE ) continue;
	  assert( ccw(C[k], C[l], C[0]) != CLOCKWISE );
	  assert( ccw(C[l], C[j], C[0]) != CLOCKWISE );
	  assert( getArea(C[j], C[l], C[0]) > 0 );

	  if ( dp[j][l][m] > dp[l][k][m-1] + getArea(C[j], C[l], C[0]) ){
	    dp[j][l][m] = dp[l][k][m-1] + getArea(C[j], C[l], C[0]);
	    pi[j][l][m] = State(l, k, m-1);
	  }


	  vector<int> a;
	  State s = State(j, l, m);
	  int last = -1;
	  while(1){
	    if ( s.j == -1 ) break;
	    a.push_back(C[s.j].id);
	    last = s.l;
	    s = pi[s.j][s.l][s.k];
	    
	  }
	  a.push_back(C[last].id);
	  a.push_back(C[0].id);
	  
	  //	  V[m].push_back(a);

	  if (  mina[m] > dp[j][l][m] ){
	    mina[m] = dp[j][l][m];
	    ans[m] = a;
	  }
	}
      }
    }
  }
}

void print(){
  assert( ans[K].size() == K );
  reverse(ans[K].begin(), ans[K].end());
  for ( int i = 0; i < ans[K].size(); i++ ){
    if (i) cout << " ";
    cout << ans[K][i];
  }
  cout << endl;

  /*
  vector<vector<int> > v = V[K];
  vector<double> r;
  for ( int i = 0; i < v.size(); i++ ){
    Polygon g;
    for ( int j = 0; j < v[i].size(); j++ ){
      g.push_back(IN[v[i][j]-1]);
    }
    double a = getArea(g);
    r.push_back(a);
  }

  sort(r.begin(), r.end());
  assert( r[0] == mina[K] );
  if ( r.size() >= 2 ){
    assert ( r[1] - r[0] >= 0.0001 );
  }
  */


  
}

void check(){
  for ( int i = 0; i < N; i++ ){
    for ( int j = 0; j < N; j++ ){
      for ( int k = 0; k < N; k++ ){
	if ( i == j ) continue;
	if ( i == k ) continue;
	if ( j == k ) continue;

	int cw = ccw(IN[i], IN[j], IN[k]);
	
	if ( ! ( cw == COUNTER_CLOCKWISE || cw == CLOCKWISE ) ){
	  assert(false);
	  cout << "hoge" << endl;
	}

      }
    }
  }
      

}


int main(){
  double x, y;
  int a, b;
  set<pair<int, int> > S;

  cin >> N;
  rep(i, N){
    //    cin >> x >> y;
    cin >> a >> b;
    S.insert( make_pair(a, b) );
    x = a;
    y = b;
    IN.push_back(Point(x, y, i+1));
  }
  sort(IN.begin(), IN.end(), yxCmp);

  check();

  assert( S.size() == N );

  int Q; cin >> Q;


  P = IN;
  rep(j, MAX) {
    mina[j] = INF;
    V[j].clear();
  }

  int s = 0;
  while( P.size() >= 3 ){
    solve(P);
    P.erase(P.begin());
  }

  rep(i, Q){
    cin >> K;
    if ( mina[K] == INF ) cout << "NA" << endl;
    else {
      print();
    }
  }
}
### Prompt

In Cpp, your task is to solve the following problem:

Let's write a program related to an unsolved math problem called "Happy End Problem". Create a program to find the smallest convex polygon formed by connecting exactly k points from the N points given on the plane. However, after being given the coordinates of N points, the question is given the number k of the angles of the convex polygon.

(Supplement: About the happy ending problem)
Place N points on the plane so that none of the three points are on the same straight line. At that time, no matter how you place the points, it is expected that if you select k points well, you will definitely be able to create a convex polygon with k corners. So far, it has been proved by 2006 that N = 3 for triangles, N = 5 for quadrilaterals, N = 9 for pentagons, and N = 17 for hexagons. There is also a prediction that N = 1 + 2k-2 for all k-sides above the triangle, but this has not yet been proven. This is a difficult problem that has been researched for 100 years.
This question has a nice name, "Happy End Problem". A friend of mathematicians named it after a man and a woman became friends while studying this issue and finally got married. It's romantic.



input

The input consists of one dataset. Input data is given in the following format.


N
x1 y1
::
xN yN
Q
k1
::
kQ


The number of points N (3 ≤ N ≤ 40) on the plane is given in the first line. The coordinates of each point are given in the following N lines. Each point is numbered from 1 to N in the order in which they are entered. xi and yi (-10000 ≤ xi, yi ≤ 10000) are integers representing the x and y coordinates of the i-th point, respectively. The positive direction of the x-axis shall be to the right, and the positive direction of the y-axis shall be upward.

The number of questions Q (1 ≤ Q ≤ N) is given in the following line. A question is given to the following Q line. ki (3 ≤ ki ≤ N) represents the number of corners of the convex polygon, which is the i-th question.

The input shall satisfy the following conditions.

* The coordinates of the input points are all different.
* None of the three points are on the same straight line.
* For each question, there is only one convex polygon with the smallest area, and the difference in area from the second smallest convex polygon is 0.0001 or more.

output

For each question, output all vertices of the convex polygon with the smallest area on one line. The number of vertices is output counterclockwise in order from the leftmost vertex among the bottom vertices of the convex polygon. Separate the vertex numbers with a single space. Do not print whitespace at the end of the line. However, if a convex polygon cannot be created, NA is output.

Example

Input

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


Output

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

### Response

```cpp
#include<iostream>
#include<cstdio>
#include<cfloat>
#include<cassert>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

#define REP(i, b, e) for ( int i = b; i < e; i++ )
#define rep(i,n) REP(i, 0, n)

#define EPS (1e-8)
#define equals(a, b) (fabs((a) - (b)) < EPS )
#define dle(a, b) (equals(a, b) || a < b )

class Point{
    public:
    double x, y;
     int id;
  Point ( double x = 0, double y = 0, int id = 0): x(x), y(y), id(id){}

    Point operator + ( Point p ){ return Point(x + p.x, y + p.y); }
    Point operator - ( Point p ){ return Point(x - p.x, y - p.y); }
    Point operator * ( double a ){ return Point(x*a, y*a); }
    Point operator / ( double a ){ return Point(x/a, y/a); }

    double abs() { return sqrt(norm());}
    double norm() { return x*x + y*y; }

    bool operator < ( const Point &p ) const {
	return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == ( const Point &p ) const {
	return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
    }
};

typedef Point Vector;

class Segment{
    public:
    Point p1, p2;
    Segment(Point s = Point(), Point t = Point()): p1(s), p2(t){}
};

typedef vector<Point> Polygon;

double norm( Vector a ){ return a.x*a.x + a.y*a.y; }
double abs( Vector a ){ return sqrt(norm(a)); }
Point polar( double a, double r ){ return Point(cos(r)*a, sin(r)*a);}
double getDistance( Vector a, Vector b ){ return abs(a - b); }
double dot( Vector a, Vector b ){ return a.x*b.x + a.y*b.y; }
double cross( Vector a, Vector b ){ return a.x*b.y - a.y*b.x; }

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw( Point p0, Point p1, Point p2 ){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if ( cross(a, b) > EPS ) return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS ) return CLOCKWISE;
    if ( dot(a, b) < -EPS ) return ONLINE_BACK;
    if ( norm(a) < norm(b) ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

double arg(Vector p){
    return atan2(p.y, p.x);
}

bool yxCmp( const Point &p1, const Point &p2 ) {
    return (p1.y == p2.y) ? p1.x < p2.x : p1.y < p2.y;
}

class PolarAngleCmp{
    public:
    Point o;
    PolarAngleCmp( Point o): o(o){}
    bool operator()( const Point &p1,  const Point &p2) const {
	Vector a = Vector(p1.x-o.x, p1.y-o.y); // p1 - o
	Vector b = Vector(p2.x-o.x, p2.y-o.y); // p2 - o
	double c = cross(a, b);
	if ( fabs(c) < EPS ) return abs(a) < abs(b);
	return c > 0;
    }
};

double getArea(Point p1, Point p2, Point p3){
    return abs(0.5 * ((p3.y-p1.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p3.x-p1.x)));
}

double getArea(Polygon p){
    double sum = 0.0;
    for(int i = 0; i < p.size(); i++){
	sum += cross(p[i], p[(i+1)%p.size()]);
    }
    return abs(sum/2);
}

class State{
public:
  int j, l, k;
  State(){}
  State(int j, int l, int k): j(j), l(l), k(k){}
};

static const int MAX = 41;
static const int INF = (1<<30);

int N, K;
vector<Point> P;
bool used[MAX];

double mina[MAX];
vector<int> ans[MAX];

vector<vector<int> > V[MAX];
  Polygon IN;

/*
 dp i, j, k
 */
void solve(vector<Point> C){
  int n = C.size();
  if ( n < 3 ) return;
  assert( C.begin() == min_element(C.begin(), C.end(), yxCmp));
  Point lm = *min_element(C.begin(), C.end(), yxCmp);
  sort(C.begin(), C.end(), PolarAngleCmp(lm));
  double dp[MAX][MAX][MAX];
  State pi[MAX][MAX][MAX];

  rep(i, n) rep(j, n) rep(k, n+1) {
    dp[i][j][k] = INF;
    pi[i][j][k] = State(-1, -1, -1);
  }

  for ( int j = 2; j < n; j++ ){
    for ( int l = j-1; l >= 1; l-- ){
      dp[j][l][3] = getArea(C[0], C[j], C[l]);

      vector<int> a;
      a.push_back(C[j].id);
      a.push_back(C[l].id);
      a.push_back(C[0].id);

      //      V[3].push_back(a);
      if ( mina[3] > dp[j][l][3] ){
	mina[3] = dp[j][l][3];
	ans[3] = a;
      }
    }
  }

  for ( int m = 4; m <= n; m++ ){
    for ( int j = 2; j < n; j++ ){ // last point
      for ( int l = j-1; l >= 1; l-- ) {
	for ( int k = l-1; k >= 0; k-- ){
	  if ( ccw(C[k], C[l], C[j]) == CLOCKWISE ) continue;
	  assert( ccw(C[k], C[l], C[0]) != CLOCKWISE );
	  assert( ccw(C[l], C[j], C[0]) != CLOCKWISE );
	  assert( getArea(C[j], C[l], C[0]) > 0 );

	  if ( dp[j][l][m] > dp[l][k][m-1] + getArea(C[j], C[l], C[0]) ){
	    dp[j][l][m] = dp[l][k][m-1] + getArea(C[j], C[l], C[0]);
	    pi[j][l][m] = State(l, k, m-1);
	  }


	  vector<int> a;
	  State s = State(j, l, m);
	  int last = -1;
	  while(1){
	    if ( s.j == -1 ) break;
	    a.push_back(C[s.j].id);
	    last = s.l;
	    s = pi[s.j][s.l][s.k];
	    
	  }
	  a.push_back(C[last].id);
	  a.push_back(C[0].id);
	  
	  //	  V[m].push_back(a);

	  if (  mina[m] > dp[j][l][m] ){
	    mina[m] = dp[j][l][m];
	    ans[m] = a;
	  }
	}
      }
    }
  }
}

void print(){
  assert( ans[K].size() == K );
  reverse(ans[K].begin(), ans[K].end());
  for ( int i = 0; i < ans[K].size(); i++ ){
    if (i) cout << " ";
    cout << ans[K][i];
  }
  cout << endl;

  /*
  vector<vector<int> > v = V[K];
  vector<double> r;
  for ( int i = 0; i < v.size(); i++ ){
    Polygon g;
    for ( int j = 0; j < v[i].size(); j++ ){
      g.push_back(IN[v[i][j]-1]);
    }
    double a = getArea(g);
    r.push_back(a);
  }

  sort(r.begin(), r.end());
  assert( r[0] == mina[K] );
  if ( r.size() >= 2 ){
    assert ( r[1] - r[0] >= 0.0001 );
  }
  */


  
}

void check(){
  for ( int i = 0; i < N; i++ ){
    for ( int j = 0; j < N; j++ ){
      for ( int k = 0; k < N; k++ ){
	if ( i == j ) continue;
	if ( i == k ) continue;
	if ( j == k ) continue;

	int cw = ccw(IN[i], IN[j], IN[k]);
	
	if ( ! ( cw == COUNTER_CLOCKWISE || cw == CLOCKWISE ) ){
	  assert(false);
	  cout << "hoge" << endl;
	}

      }
    }
  }
      

}


int main(){
  double x, y;
  int a, b;
  set<pair<int, int> > S;

  cin >> N;
  rep(i, N){
    //    cin >> x >> y;
    cin >> a >> b;
    S.insert( make_pair(a, b) );
    x = a;
    y = b;
    IN.push_back(Point(x, y, i+1));
  }
  sort(IN.begin(), IN.end(), yxCmp);

  check();

  assert( S.size() == N );

  int Q; cin >> Q;


  P = IN;
  rep(j, MAX) {
    mina[j] = INF;
    V[j].clear();
  }

  int s = 0;
  while( P.size() >= 3 ){
    solve(P);
    P.erase(P.begin());
  }

  rep(i, Q){
    cin >> K;
    if ( mina[K] == INF ) cout << "NA" << endl;
    else {
      print();
    }
  }
}
```