#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define eb emplace_back 
#define lb lower_bound 
#define fi first
#define se second

#define rep(i, a, b) for (auto i = (a); i < (b); ++i) // [a, b)
#define trav(e, x) for (auto &e : x)

#define getchar getchar_unlocked
#define putchar putchar_unlocked

inline int in() {
	int n, c, flag = 1;
	while ((c = getchar()) < '0') if (c == EOF) return -1; else flag = -1;
	n = c - '0';
	while ((c = getchar()) >= '0') n = n * 10 + c - '0';
	return n * flag;
}

inline void out(int n) {
	int res[10], i = 0;
	do { res[i++] = n % 10, n /= 10; } while (n);
	while (i) putchar(res[--i] + '0');
	putchar('\n');
}

signed main() {
	int n = in();
	vector<pii> p(n); trav(q, p) q.fi = in(), q.se = in();
	vector<int> x(n); rep(i, 0, n) x[i] = p[i].fi;
	sort(all(x)); x.erase(unique(all(x)), end(x));
	vector<vector<pii>> y(sz(x));
	rep(i, 0, n) {
		int j = lb(all(x), p[i].fi) - begin(x);
		y[j].eb(p[i].se, i);
	}
	trav(v, y) sort(all(v));
	int t = in();
	while (t--) {
		vi ans;
		int sx = in(), tx = in(), sy = in(), ty = in();
		int l = lb(all(x), sx) - begin(x);
		rep(i, l, sz(x)) {
			if (x[i] > tx) break;
			int a = lb(all(y[i]), pii(sy, 0)) - begin(y[i]);
			rep(j, a, sz(y[i])) {
				if (y[i][j].fi > ty) break;
				ans.eb(y[i][j].se);
			}
		}
		sort(all(ans)); trav(x, ans) out(x); putchar('\n');
	}
}

### Prompt

Create a solution in CPP for the following problem:

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 <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define eb emplace_back 
#define lb lower_bound 
#define fi first
#define se second

#define rep(i, a, b) for (auto i = (a); i < (b); ++i) // [a, b)
#define trav(e, x) for (auto &e : x)

#define getchar getchar_unlocked
#define putchar putchar_unlocked

inline int in() {
	int n, c, flag = 1;
	while ((c = getchar()) < '0') if (c == EOF) return -1; else flag = -1;
	n = c - '0';
	while ((c = getchar()) >= '0') n = n * 10 + c - '0';
	return n * flag;
}

inline void out(int n) {
	int res[10], i = 0;
	do { res[i++] = n % 10, n /= 10; } while (n);
	while (i) putchar(res[--i] + '0');
	putchar('\n');
}

signed main() {
	int n = in();
	vector<pii> p(n); trav(q, p) q.fi = in(), q.se = in();
	vector<int> x(n); rep(i, 0, n) x[i] = p[i].fi;
	sort(all(x)); x.erase(unique(all(x)), end(x));
	vector<vector<pii>> y(sz(x));
	rep(i, 0, n) {
		int j = lb(all(x), p[i].fi) - begin(x);
		y[j].eb(p[i].se, i);
	}
	trav(v, y) sort(all(v));
	int t = in();
	while (t--) {
		vi ans;
		int sx = in(), tx = in(), sy = in(), ty = in();
		int l = lb(all(x), sx) - begin(x);
		rep(i, l, sz(x)) {
			if (x[i] > tx) break;
			int a = lb(all(y[i]), pii(sy, 0)) - begin(y[i]);
			rep(j, a, sz(y[i])) {
				if (y[i][j].fi > ty) break;
				ans.eb(y[i][j].se);
			}
		}
		sort(all(ans)); trav(x, ans) out(x); putchar('\n');
	}
}

```