#include<bits/stdc++.h>
using namespace std;
const int sz = 1 << 16;
typedef pair< int, int > Pi;
vector< Pi > seg[2 * sz + 1];
int x[500000], y[500000];
int sx[20000], sy[20000], tx[20000], ty[20000];
vector< pair< int, Pi > > buff;
vector< int > nums;
vector< int > ret;
void InitRange(int k, int l, int r) {
  if(l + 1 >= r) {
    return;
  } else {
    InitRange(2 * k + 1, l, (l + r) >> 1);
    InitRange(2 * k + 2, (l + r) >> 1, r);
    if(k >= 114) {
      seg[k].assign(seg[2 * k + 1].size() + seg[2 * k + 2].size(), Pi());
      merge(seg[2 * k + 1].begin(), seg[2 * k + 1].end(), seg[2 * k + 2].begin(), seg[2 * k + 2].end(), seg[k].begin());
    }
  }
}
  
void PrintRange(int a, int b, int low, int high, int k, int l, int r) {
  if(a >= r || b <= l) {
    return;
  } else if(a <= l && r <= b && k >= 114) {
    for(vector< Pi >::iterator it = lower_bound(seg[k].begin(), seg[k].end(), Pi(low, -1)); it != seg[k].end() && it -> first <= high; it++) { 
      ret.push_back(it -> second);
    }
  } else {
    PrintRange(a, b, low, high, 2 * k + 1, l, (l + r) >> 1);
    PrintRange(a, b, low, high, 2 * k + 2, (l + r) >> 1, r);
  }
}
  
int main() {
  int n, q;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d %d", &x[i], &y[i]);
  }
  scanf("%d", &q);
  for(int i = 0; i < q; i++) {
    scanf("%d %d %d %d", &sx[i], &tx[i], &sy[i], &ty[i]);
    nums.push_back(sx[i]);
    nums.push_back(sx[i] - 1);
    nums.push_back(tx[i]);
  }
  sort(nums.begin(), nums.end());
  nums.erase(unique(nums.begin(), nums.end()), nums.end());
  for(int i = 0; i < n; i++) {
    x[i] = lower_bound(nums.begin(), nums.end(), x[i]) - nums.begin();
    buff.push_back(make_pair(x[i], make_pair(y[i], i)));
  }
  sort(buff.begin(), buff.end());
  for(int i = 0; i < n; i++) {
    seg[buff[i].first + sz - 1].push_back(buff[i].second);
  }
  InitRange(0, 0, sz);
 
  for(int i = 0; i < q; i++) {
    ret.clear();
    sx[i] = lower_bound(nums.begin(), nums.end(), sx[i]) - nums.begin();
    tx[i] = upper_bound(nums.begin(), nums.end(), tx[i]) - nums.begin();
  
    PrintRange(sx[i], tx[i], sy[i], ty[i], 0, 0, sz);
    sort(ret.begin(), ret.end());
    for(vector< int >::const_iterator it = ret.begin(); it != ret.end(); it++) {
      printf("%d\n", *it);
    }
    printf("\n");
  }
  
}
### Prompt

Generate a CPP solution to 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;
const int sz = 1 << 16;
typedef pair< int, int > Pi;
vector< Pi > seg[2 * sz + 1];
int x[500000], y[500000];
int sx[20000], sy[20000], tx[20000], ty[20000];
vector< pair< int, Pi > > buff;
vector< int > nums;
vector< int > ret;
void InitRange(int k, int l, int r) {
  if(l + 1 >= r) {
    return;
  } else {
    InitRange(2 * k + 1, l, (l + r) >> 1);
    InitRange(2 * k + 2, (l + r) >> 1, r);
    if(k >= 114) {
      seg[k].assign(seg[2 * k + 1].size() + seg[2 * k + 2].size(), Pi());
      merge(seg[2 * k + 1].begin(), seg[2 * k + 1].end(), seg[2 * k + 2].begin(), seg[2 * k + 2].end(), seg[k].begin());
    }
  }
}
  
void PrintRange(int a, int b, int low, int high, int k, int l, int r) {
  if(a >= r || b <= l) {
    return;
  } else if(a <= l && r <= b && k >= 114) {
    for(vector< Pi >::iterator it = lower_bound(seg[k].begin(), seg[k].end(), Pi(low, -1)); it != seg[k].end() && it -> first <= high; it++) { 
      ret.push_back(it -> second);
    }
  } else {
    PrintRange(a, b, low, high, 2 * k + 1, l, (l + r) >> 1);
    PrintRange(a, b, low, high, 2 * k + 2, (l + r) >> 1, r);
  }
}
  
int main() {
  int n, q;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d %d", &x[i], &y[i]);
  }
  scanf("%d", &q);
  for(int i = 0; i < q; i++) {
    scanf("%d %d %d %d", &sx[i], &tx[i], &sy[i], &ty[i]);
    nums.push_back(sx[i]);
    nums.push_back(sx[i] - 1);
    nums.push_back(tx[i]);
  }
  sort(nums.begin(), nums.end());
  nums.erase(unique(nums.begin(), nums.end()), nums.end());
  for(int i = 0; i < n; i++) {
    x[i] = lower_bound(nums.begin(), nums.end(), x[i]) - nums.begin();
    buff.push_back(make_pair(x[i], make_pair(y[i], i)));
  }
  sort(buff.begin(), buff.end());
  for(int i = 0; i < n; i++) {
    seg[buff[i].first + sz - 1].push_back(buff[i].second);
  }
  InitRange(0, 0, sz);
 
  for(int i = 0; i < q; i++) {
    ret.clear();
    sx[i] = lower_bound(nums.begin(), nums.end(), sx[i]) - nums.begin();
    tx[i] = upper_bound(nums.begin(), nums.end(), tx[i]) - nums.begin();
  
    PrintRange(sx[i], tx[i], sy[i], ty[i], 0, 0, sz);
    sort(ret.begin(), ret.end());
    for(vector< int >::const_iterator it = ret.begin(); it != ret.end(); it++) {
      printf("%d\n", *it);
    }
    printf("\n");
  }
  
}
```