#include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>

struct point{ int x, y, id; };

point init(int pos_x, int pos_y, int index)
{
	point p; 
	p.x = pos_x, p.y = pos_y, p.id = index; 
	return p; 
}

bool cmp_x(const point &P1, const point &P2){ if(P1.x != P2.x){ return P1.x < P2.x; } return P1.y < P2.y; }
bool cmp_y(const point &P1, const point &P2){ if(P1.y != P2.y){ return P1.y < P2.y; } return P1.x < P2.x; }

void kd_tree(point *S, point *T, point *U, int left, int right, int d)
{
	if(right - left < 2) return;

	int mid = ((left + right) >> 1);
	int a = left, b = mid + 1;

	if((d & 1) == 0){
		for(int i = left; i < right; i++){
			if(cmp_x(T[i], S[mid])){
				U[a++] = T[i];
			}else if(S[mid].id == T[i].id){
				U[mid] = T[i];
			}else{
				U[b++] = T[i];
			}
		}
		for(int i = left; i < right; i++){ T[i] = U[i]; }

	}else{
		for(int i = left; i < right; i++){
			if(cmp_y(S[i], T[mid])){
				U[a++] = S[i];
			}else if(T[mid].id == S[i].id){
				U[mid] = S[i];
			}else{
				U[b++] = S[i];
			}
		}
		for(int i = left; i < right; i++){ S[i] = U[i]; }
	}
	kd_tree(S, T, U, left, mid, d + 1);
	kd_tree(S, T, U, mid + 1, right, d + 1);
}

int cnt;

void find_pt(int *Q, point *S, int sx, int tx, int sy, int ty, int left, int right, int d)
{
	if(left >= right) return;

	int mid = ((left + right) >> 1);
	point p = S[mid];
	int a = p.x, b = p.y;

	if(sx <= a && a <= tx && sy <= b && b <= ty){
		Q[cnt++] = p.id;
	}

	if((d & 1) == 0){
		if((left < mid) && (sx < a || (sx == a && sy <= b))){ find_pt(Q, S, sx, tx, sy, ty, left, mid, d + 1); }
		if((mid + 1 < right) && (a < tx || (a == tx && b <= ty))){ find_pt(Q, S, sx, tx, sy, ty, mid + 1, right, d + 1); }
	}else{
		if((left < mid) && (sy < b || (sy == b && sx <= a))){ find_pt(Q, S, sx, tx, sy, ty, left, mid, d + 1); }
		if((mid + 1 < right) && (b < ty || (b == ty && a <= tx))){ find_pt(Q, S, sx, tx, sy, ty, mid + 1, right, d + 1); }
	}
	return;
}

int main()
{
	point *S, *T, *U;
	int Q[100];
	int i, pos_x, pos_y, n;
	scanf("%d", &n);

	S = new point [n], T = new point [n], U = new point [n];

	for(i = 0; i < n; i++){
		scanf("%d %d", &pos_x, &pos_y);
		S[i] = init(pos_x, pos_y, i);
		T[i] = S[i];
	}
	sort(S, S + n, cmp_x);
	sort(T, T + n, cmp_y);

	kd_tree(S, T, U, 0, n, 0);

	int sx, tx, sy, ty, q;
	scanf("%d", &q);
	while(q){
		cnt = 0;
		scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
		find_pt(Q, S, sx, tx, sy, ty, 0, n, 0);
		sort(Q, Q + cnt);
		for(int i = 0; i < cnt; i++){ printf("%d\n", Q[i]); }
		printf("\n");
		q--;
	}

	return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

The range search problem consists of a set of attributed records S to determine which records from S intersect with a given range.

For n points on a plane, report a set of points which are within in a given range. Note that you do not need to consider insert and delete operations for the set.

Constraints

* 0 ≤ n ≤ 500,000
* 0 ≤ q ≤ 20,000
* -1,000,000,000 ≤ x, y, sx, tx, sy, ty ≤ 1,000,000,000
* sx ≤ tx
* sy ≤ ty
* For each query, the number of points which are within the range is less than or equal to 100.

Input


n
x0 y0
x1 y1
:
xn-1 yn-1
q
sx0 tx0 sy0 ty0
sx1 tx1 sy1 ty1
:
sxq-1 txq-1 syq-1 tyq-1


The first integer n is the number of points. In the following n lines, the coordinate of the i-th point is given by two integers xi and yi.

The next integer q is the number of queries. In the following q lines, each query is given by four integers, sxi, txi, syi, tyi.

Output

For each query, report IDs of points such that sxi ≤ x ≤ txi and syi ≤ y ≤ tyi. The IDs should be reported in ascending order. Print an ID in a line, and print a blank line at the end of output for the each query.

Example

Input

6
2 1
2 2
4 2
6 2
3 3
5 4
2
2 4 0 4
4 10 2 5


Output

0
1
2
4

2
3
5

### Response

```cpp
#include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>

struct point{ int x, y, id; };

point init(int pos_x, int pos_y, int index)
{
	point p; 
	p.x = pos_x, p.y = pos_y, p.id = index; 
	return p; 
}

bool cmp_x(const point &P1, const point &P2){ if(P1.x != P2.x){ return P1.x < P2.x; } return P1.y < P2.y; }
bool cmp_y(const point &P1, const point &P2){ if(P1.y != P2.y){ return P1.y < P2.y; } return P1.x < P2.x; }

void kd_tree(point *S, point *T, point *U, int left, int right, int d)
{
	if(right - left < 2) return;

	int mid = ((left + right) >> 1);
	int a = left, b = mid + 1;

	if((d & 1) == 0){
		for(int i = left; i < right; i++){
			if(cmp_x(T[i], S[mid])){
				U[a++] = T[i];
			}else if(S[mid].id == T[i].id){
				U[mid] = T[i];
			}else{
				U[b++] = T[i];
			}
		}
		for(int i = left; i < right; i++){ T[i] = U[i]; }

	}else{
		for(int i = left; i < right; i++){
			if(cmp_y(S[i], T[mid])){
				U[a++] = S[i];
			}else if(T[mid].id == S[i].id){
				U[mid] = S[i];
			}else{
				U[b++] = S[i];
			}
		}
		for(int i = left; i < right; i++){ S[i] = U[i]; }
	}
	kd_tree(S, T, U, left, mid, d + 1);
	kd_tree(S, T, U, mid + 1, right, d + 1);
}

int cnt;

void find_pt(int *Q, point *S, int sx, int tx, int sy, int ty, int left, int right, int d)
{
	if(left >= right) return;

	int mid = ((left + right) >> 1);
	point p = S[mid];
	int a = p.x, b = p.y;

	if(sx <= a && a <= tx && sy <= b && b <= ty){
		Q[cnt++] = p.id;
	}

	if((d & 1) == 0){
		if((left < mid) && (sx < a || (sx == a && sy <= b))){ find_pt(Q, S, sx, tx, sy, ty, left, mid, d + 1); }
		if((mid + 1 < right) && (a < tx || (a == tx && b <= ty))){ find_pt(Q, S, sx, tx, sy, ty, mid + 1, right, d + 1); }
	}else{
		if((left < mid) && (sy < b || (sy == b && sx <= a))){ find_pt(Q, S, sx, tx, sy, ty, left, mid, d + 1); }
		if((mid + 1 < right) && (b < ty || (b == ty && a <= tx))){ find_pt(Q, S, sx, tx, sy, ty, mid + 1, right, d + 1); }
	}
	return;
}

int main()
{
	point *S, *T, *U;
	int Q[100];
	int i, pos_x, pos_y, n;
	scanf("%d", &n);

	S = new point [n], T = new point [n], U = new point [n];

	for(i = 0; i < n; i++){
		scanf("%d %d", &pos_x, &pos_y);
		S[i] = init(pos_x, pos_y, i);
		T[i] = S[i];
	}
	sort(S, S + n, cmp_x);
	sort(T, T + n, cmp_y);

	kd_tree(S, T, U, 0, n, 0);

	int sx, tx, sy, ty, q;
	scanf("%d", &q);
	while(q){
		cnt = 0;
		scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
		find_pt(Q, S, sx, tx, sy, ty, 0, n, 0);
		sort(Q, Q + cnt);
		for(int i = 0; i < cnt; i++){ printf("%d\n", Q[i]); }
		printf("\n");
		q--;
	}

	return 0;
}
```