#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-6;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const double INF = 1e15;

class Point{
public:
  double x, y;

  Point(double x = 0.0, double y = 0.0) : x(x), y(y){}

  Point& operator += (const Point& p){ x += p.x; y += p.y; return *this;}
  Point operator + (const Point& p) const{ Point q = *this;return q += p;}
  Point& operator -= (const Point& p){ x -= p.x; y -= p.y; return *this;}
  Point operator - (const Point& p) const{ Point q = *this; return q -= p;}
  Point& operator *= (double a){ x *= a; y *= a; return *this;}
  Point operator * (double a) const{ Point q = *this; return q *= a;}
  Point& operator /= (double a){ x /= a; y /= a; return *this;}
  Point operator / (double a) const{ Point q = *this; return q /= a;}

  double abs() const { return sqrt(norm()); }
  double norm() const { return x*x + y*y; }
  Point& normalize(){ return *this /= abs(); }
  
  bool operator < (const Point &p) const{
	return y != p.y ? y < p.y : x < p.x;
  }
  
  //EPSは十分小さな値
  bool operator == (const Point &p) const {
	return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
  }
  friend ostream& operator <<(ostream& os, const Point& p);
};
ostream& operator <<(ostream& os, const Point& p){
  return os << "(" << p.x << ","<<p.y << ")";
}

typedef vector<Point> Polygon;
typedef Point Vector;
//内積
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;
}

int ccw(Point p0, Point p1, Point p2){

	//p0->p1をp0始点、p1終点の基準ベクトルとしたとき

	//p0->p2が反時計回りになるとき
	static const int COUNTER_CLOCKWISE = 1;
	//p0->p2が時計回りになるとき
	static const int CLOCKWISE = -1;
	//p2,p0,p1の順で同一直線上にあるとき
	static const int ONLINE_BACK = 2;
	//p0,p1,p2 の順で同一直線上にある場合
	static const int ONLINE_FRONT = -2;
	//p2 が線分 p0p1 上にある場合
	static const int ON_SEGMENT = 0;

	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 (a.norm() < b.norm()) return ONLINE_FRONT;

	return ON_SEGMENT;
}
Polygon andrewScan(Polygon s){
	Polygon u, l;

	if (s.size() < 3) return s;

	sort(s.begin(), s.end()); //x,yを基準にソート

	u.push_back(s[0]);
	u.push_back(s[1]);

	l.push_back(s[s.size() - 1]);
	l.push_back(s[s.size() - 2]);

	//凸方の上部を生成
	for (unsigned int i = 2; i < s.size(); i++){
		for (int n = u.size(); n >= 2 && ccw(u[n - 2], u[n - 1], s[i]) == 1; n--){
			u.pop_back();
		}
		u.push_back(s[i]);
	}

	//凸法の下部を生成
	for (int i = s.size() - 3; i >= 0; i--){
		for (int n = l.size(); n >= 2 && ccw(l[n - 2], l[n - 1], s[i]) == 1; n--){
			l.pop_back();
		}
		l.push_back(s[i]);
	}

	//反時計回りになるように凸包の点の列
	reverse(l.begin(), l.end());
	for (int i = u.size() - 2; i >= 1; i--)
		l.push_back(u[i]);

	return l;
}

double tri_area(Point p1, Point p2, Point p3){
  return abs(cross(p2-p1, p3-p1)) / 2.;
}

double dp[41][41][41][41];
int rev[41][41][41][41];

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<pair<Point,int>> ps(N);
  REP(i,N){
	cin >> ps[i].FF.x >> ps[i].FF.y;
	ps[i].SS = i+1;
  }
  SORT(ps);

  fill((double*)dp, (double*)dp+41*41*41*41, INF);
  REP(i1,N) REP(i2,N) REP(i3,N){
	if(i1==i2 || i2 == i3 || i1==i3) continue;
	if(ps[i2] < ps[i1] || ps[i3] < ps[i1]) continue;
	if(ccw(ps[i1].FF, ps[i2].FF, ps[i3].FF) == 1){
	  dp[3][i1][i2][i3] = tri_area(ps[i1].FF, ps[i2].FF, ps[i3].FF);
	}
  }

  FOR(i,3,N) REP(b,N) REP(j,N) REP(k,N){
	if(dp[i][b][j][k] >= INF) continue;
	FOR(n,b+1,N){
	  if(n == b || n == j || n == k) continue;
	  if(ccw(ps[j].FF, ps[k].FF, ps[n].FF) != 1 || ccw(ps[b].FF, ps[n].FF, ps[k].FF) != -1) continue;
	  double res = dp[i][b][j][k] + tri_area(ps[k].FF, ps[n].FF, ps[b].FF);
	  if(res < dp[i+1][b][k][n]){
		dp[i+1][b][k][n] = res;
		rev[i+1][b][k][n] = j;
	  }
	}
  }

  int Q;
  cin >> Q;
  REP(q,Q){
	int K;
	cin >> K;

	int ab=-1, aj, ak;
	double best = INF;
	REP(b,N) REP(j,N) REP(k,N){
	  if(dp[K][b][j][k] >= INF) continue;
	  if(dp[K][b][j][k] <= best-EPS){
		best = dp[K][b][j][k];
		ab = b;
		aj = j;
		ak = k;
	  }
	  else if(abs(dp[K][b][j][k] - best) <= EPS){
		if(ps[b] < ps[ab]){
		  best = dp[K][b][j][k];
		  ab = b;
		  aj = j;
		  ak = k;
		}
	  }
	}
	if(ab == -1){
	  cout << "NA" << endl;
	  continue;
	}

	VI ans;
	for(int k=K;k>3;--k){
	  ans.PB(ps[ak].SS);
	  int r = rev[k][ab][aj][ak];
	  ak = aj;
	  aj = r;
	}
	ans.PB(ps[ak].SS);
	ans.PB(ps[aj].SS);
	ans.PB(ps[ab].SS);
	reverse(ALL(ans));
	cout << ans << endl;
  }

  return 0;
}


### Prompt

Your challenge is to write a Cpp solution to 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 <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-6;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const double INF = 1e15;

class Point{
public:
  double x, y;

  Point(double x = 0.0, double y = 0.0) : x(x), y(y){}

  Point& operator += (const Point& p){ x += p.x; y += p.y; return *this;}
  Point operator + (const Point& p) const{ Point q = *this;return q += p;}
  Point& operator -= (const Point& p){ x -= p.x; y -= p.y; return *this;}
  Point operator - (const Point& p) const{ Point q = *this; return q -= p;}
  Point& operator *= (double a){ x *= a; y *= a; return *this;}
  Point operator * (double a) const{ Point q = *this; return q *= a;}
  Point& operator /= (double a){ x /= a; y /= a; return *this;}
  Point operator / (double a) const{ Point q = *this; return q /= a;}

  double abs() const { return sqrt(norm()); }
  double norm() const { return x*x + y*y; }
  Point& normalize(){ return *this /= abs(); }
  
  bool operator < (const Point &p) const{
	return y != p.y ? y < p.y : x < p.x;
  }
  
  //EPSは十分小さな値
  bool operator == (const Point &p) const {
	return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
  }
  friend ostream& operator <<(ostream& os, const Point& p);
};
ostream& operator <<(ostream& os, const Point& p){
  return os << "(" << p.x << ","<<p.y << ")";
}

typedef vector<Point> Polygon;
typedef Point Vector;
//内積
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;
}

int ccw(Point p0, Point p1, Point p2){

	//p0->p1をp0始点、p1終点の基準ベクトルとしたとき

	//p0->p2が反時計回りになるとき
	static const int COUNTER_CLOCKWISE = 1;
	//p0->p2が時計回りになるとき
	static const int CLOCKWISE = -1;
	//p2,p0,p1の順で同一直線上にあるとき
	static const int ONLINE_BACK = 2;
	//p0,p1,p2 の順で同一直線上にある場合
	static const int ONLINE_FRONT = -2;
	//p2 が線分 p0p1 上にある場合
	static const int ON_SEGMENT = 0;

	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 (a.norm() < b.norm()) return ONLINE_FRONT;

	return ON_SEGMENT;
}
Polygon andrewScan(Polygon s){
	Polygon u, l;

	if (s.size() < 3) return s;

	sort(s.begin(), s.end()); //x,yを基準にソート

	u.push_back(s[0]);
	u.push_back(s[1]);

	l.push_back(s[s.size() - 1]);
	l.push_back(s[s.size() - 2]);

	//凸方の上部を生成
	for (unsigned int i = 2; i < s.size(); i++){
		for (int n = u.size(); n >= 2 && ccw(u[n - 2], u[n - 1], s[i]) == 1; n--){
			u.pop_back();
		}
		u.push_back(s[i]);
	}

	//凸法の下部を生成
	for (int i = s.size() - 3; i >= 0; i--){
		for (int n = l.size(); n >= 2 && ccw(l[n - 2], l[n - 1], s[i]) == 1; n--){
			l.pop_back();
		}
		l.push_back(s[i]);
	}

	//反時計回りになるように凸包の点の列
	reverse(l.begin(), l.end());
	for (int i = u.size() - 2; i >= 1; i--)
		l.push_back(u[i]);

	return l;
}

double tri_area(Point p1, Point p2, Point p3){
  return abs(cross(p2-p1, p3-p1)) / 2.;
}

double dp[41][41][41][41];
int rev[41][41][41][41];

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<pair<Point,int>> ps(N);
  REP(i,N){
	cin >> ps[i].FF.x >> ps[i].FF.y;
	ps[i].SS = i+1;
  }
  SORT(ps);

  fill((double*)dp, (double*)dp+41*41*41*41, INF);
  REP(i1,N) REP(i2,N) REP(i3,N){
	if(i1==i2 || i2 == i3 || i1==i3) continue;
	if(ps[i2] < ps[i1] || ps[i3] < ps[i1]) continue;
	if(ccw(ps[i1].FF, ps[i2].FF, ps[i3].FF) == 1){
	  dp[3][i1][i2][i3] = tri_area(ps[i1].FF, ps[i2].FF, ps[i3].FF);
	}
  }

  FOR(i,3,N) REP(b,N) REP(j,N) REP(k,N){
	if(dp[i][b][j][k] >= INF) continue;
	FOR(n,b+1,N){
	  if(n == b || n == j || n == k) continue;
	  if(ccw(ps[j].FF, ps[k].FF, ps[n].FF) != 1 || ccw(ps[b].FF, ps[n].FF, ps[k].FF) != -1) continue;
	  double res = dp[i][b][j][k] + tri_area(ps[k].FF, ps[n].FF, ps[b].FF);
	  if(res < dp[i+1][b][k][n]){
		dp[i+1][b][k][n] = res;
		rev[i+1][b][k][n] = j;
	  }
	}
  }

  int Q;
  cin >> Q;
  REP(q,Q){
	int K;
	cin >> K;

	int ab=-1, aj, ak;
	double best = INF;
	REP(b,N) REP(j,N) REP(k,N){
	  if(dp[K][b][j][k] >= INF) continue;
	  if(dp[K][b][j][k] <= best-EPS){
		best = dp[K][b][j][k];
		ab = b;
		aj = j;
		ak = k;
	  }
	  else if(abs(dp[K][b][j][k] - best) <= EPS){
		if(ps[b] < ps[ab]){
		  best = dp[K][b][j][k];
		  ab = b;
		  aj = j;
		  ak = k;
		}
	  }
	}
	if(ab == -1){
	  cout << "NA" << endl;
	  continue;
	}

	VI ans;
	for(int k=K;k>3;--k){
	  ans.PB(ps[ak].SS);
	  int r = rev[k][ab][aj][ak];
	  ak = aj;
	  aj = r;
	}
	ans.PB(ps[ak].SS);
	ans.PB(ps[aj].SS);
	ans.PB(ps[ab].SS);
	reverse(ALL(ans));
	cout << ans << endl;
  }

  return 0;
}


```