#include <bits/stdc++.h>
using namespace std;
const int N = 100050;
const int M = 2 * N;
const int L = 18;
struct vec2 {
  long long x, y;
  int idx;
  vec2() {}
  vec2(long long a, long long b) : x(a), y(b) {}
  vec2 operator-(vec2 other) const { return vec2(x - other.x, y - other.y); }
};
bool cmp(vec2 a, vec2 b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
long long cross(vec2 a, vec2 b) { return a.x * b.y - a.y * b.x; }
int part(vec2 a) { return (a.x > 0 || (a.x == 0 && a.y > 0)) ? 0 : 1; }
bool operator<(vec2 a, vec2 b) {
  int pa = part(a), push_back = part(b);
  if (pa != push_back) return pa < push_back;
  return cross(a, b) > 0;
}
struct DecrementalHull {
  int ls[M], rs[M], tsz, root;
  int ss[M], se[M];
  int ul[M], ur[M];
  int bl[M], br[M];
  int n;
  vector<vec2> pts;
  DecrementalHull() {}
  bool ccw(int i, int j, int k) {
    return cross(pts[j] - pts[i], pts[k] - pts[i]) > 0;
  }
  void pull(int c) {
    int p = ls[c], q = rs[c];
    long long sx = pts[ss[q]].x;
    while (ul[p] != ur[p] || ul[q] != ur[q]) {
      int A = ul[p], B = ur[p];
      int C = ul[q], D = ur[q];
      if (B != A && !ccw(C, B, A))
        p = ls[p];
      else if (C != D && !ccw(D, C, B))
        q = rs[q];
      else if (A == B)
        q = ls[q];
      else if (C == D)
        p = rs[p];
      else {
        long long c1 = cross(pts[B] - pts[A], pts[C] - pts[A]);
        long long c2 = cross(pts[A] - pts[B], pts[D] - pts[B]);
        if (c1 + c2 == 0 || c1 * pts[D].x + c2 * pts[C].x < sx * (c1 + c2))
          p = rs[p];
        else
          q = ls[q];
      }
    }
    ul[c] = ss[p];
    ur[c] = ss[q];
    p = ls[c], q = rs[c];
    while (bl[p] != br[p] || bl[q] != br[q]) {
      int A = bl[p], B = br[p];
      int C = bl[q], D = br[q];
      if (B != A && !ccw(A, B, C))
        p = ls[p];
      else if (C != D && !ccw(B, C, D))
        q = rs[q];
      else if (A == B)
        q = ls[q];
      else if (C == D)
        p = rs[p];
      else {
        long long c1 = cross(pts[B] - pts[A], pts[C] - pts[A]);
        long long c2 = cross(pts[A] - pts[B], pts[D] - pts[B]);
        if (c1 + c2 == 0 || c1 * pts[D].x + c2 * pts[C].x > sx * (c1 + c2))
          p = rs[p];
        else
          q = ls[q];
      }
    }
    bl[c] = ss[p];
    br[c] = ss[q];
    ss[c] = ss[ls[c]];
    se[c] = se[rs[c]];
  }
  void Build(int& c, int l, int r) {
    c = ++tsz;
    ss[c] = l;
    se[c] = r;
    if (l == r) {
      ul[c] = ur[c] = l;
      bl[c] = br[c] = l;
      return;
    }
    int mid = l + r >> 1;
    Build(ls[c], l, mid);
    Build(rs[c], mid + 1, r);
    pull(c);
  }
  void Build() {
    sort(pts.begin(), pts.end(), cmp);
    n = pts.size();
    Build(root, 0, n - 1);
  }
  void Del(int& c, int qi) {
    if (ss[c] == se[c])
      c = 0;
    else {
      if (qi <= se[ls[c]])
        Del(ls[c], qi);
      else
        Del(rs[c], qi);
      if (!ls[c])
        c = rs[c];
      else if (!rs[c])
        c = ls[c];
      else
        pull(c);
    }
  }
  vector<vec2> hull;
  vector<int> top, bot, ids;
  void GetTop(int c, int l, int r) {
    if (ul[c] == ur[c]) {
      top.push_back(ss[c]);
    } else if (ul[c] >= r) {
      GetTop(ls[c], l, r);
    } else if (ur[c] <= l) {
      GetTop(rs[c], l, r);
    } else {
      GetTop(rs[c], ur[c], r);
      GetTop(ls[c], l, ul[c]);
    }
  }
  void GetBot(int c, int l, int r) {
    if (bl[c] == br[c]) {
      bot.push_back(ss[c]);
    } else if (bl[c] >= r) {
      GetBot(ls[c], l, r);
    } else if (br[c] <= l) {
      GetBot(rs[c], l, r);
    } else {
      GetBot(ls[c], l, bl[c]);
      GetBot(rs[c], br[c], r);
    }
  }
  vector<vec2> GetHull() {
    top.clear();
    bot.clear();
    GetTop(root, 0, n - 1);
    GetBot(root, 0, n - 1);
    ids.clear();
    for (int i : bot) ids.push_back(i);
    for (int i : top)
      if (ids.back() != i && ids.front() != i) ids.push_back(i);
    hull.clear();
    for (int i : ids) hull.push_back(pts[i]);
    for (int i : ids) Del(root, i);
    return hull;
  }
} DH;
int n, q;
vec2 pts[N];
vector<vector<vec2>> layers;
vector<vec2> slopes;
vector<int> pref;
int go[N][L], idx[N];
void buildConvexHullLayers() {
  for (int i = 1; i <= n; i++) DH.pts.push_back(pts[i]);
  DH.Build();
  while (DH.root != 0) {
    vector<vec2> layer = DH.GetHull();
    for (int i = 0; i < layer.size(); i++) idx[layer[i].idx] = i;
    layers.push_back(layer);
  }
  int sz = layers[0].size();
  for (int i = 0; i < sz; i++) {
    slopes.push_back(layers[0][(i + 1) % sz] - layers[0][i]);
  }
}
void buildLayerConnections() {
  for (int i = 0; i + 1 < layers.size(); i++) {
    vector<vec2> layer = layers[i];
    vector<vec2> nextl = layers[i + 1];
    int lsz = layer.size(), ptr = 0;
    auto nxt = [&](int x) { return x + 1 == nextl.size() ? 0 : x + 1; };
    auto pre = [&](int x) { return x == 0 ? nextl.size() - 1 : x - 1; };
    for (int j = 0; j < lsz; j++) {
      vec2 src = layer[j == 0 ? lsz - 1 : j - 1];
      while (cross(nextl[ptr] - src, nextl[nxt(ptr)] - src) < 0) ptr = nxt(ptr);
      while (cross(nextl[ptr] - src, nextl[pre(ptr)] - src) < 0) ptr = pre(ptr);
      go[layer[j].idx][0] = nextl[ptr].idx;
    }
  }
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n; i++) {
      go[i][j] = go[go[i][j - 1]][j - 1];
    }
  }
  pref.reserve(layers.size() + 1);
  pref.push_back(0);
  for (int i = 0; i < layers.size(); i++) {
    pref.push_back(pref.back() + layers[i].size());
  }
}
int getFirst(vec2 dir) {
  int idx = lower_bound(slopes.begin(), slopes.end(), dir) - slopes.begin();
  if (idx == slopes.size()) idx = 0;
  return layers[0][idx].idx;
}
int getDestLayer(int k) {
  return lower_bound(pref.begin(), pref.end(), k) - pref.begin() - 1;
}
int walkCCW(int layer, int start, int steps) {
  int layer_size = layers[layer].size();
  return layers[layer][(idx[start] + steps) % layer_size].idx;
}
int main() {
  scanf("%i", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &pts[i].x, &pts[i].y);
    pts[i].idx = i;
  }
  buildConvexHullLayers();
  buildLayerConnections();
  scanf("%i", &q);
  while (q--) {
    vec2 dir;
    int k;
    scanf("%lld %lld %i", &dir.x, &dir.y, &k);
    int idx = getFirst(dir);
    int destLayer = getDestLayer(k);
    for (int j = 0; j < L; j++)
      if (destLayer >> j & 1) idx = go[idx][j];
    int ost = k - pref[destLayer];
    int ans = walkCCW(destLayer, idx, ost - 1);
    printf("%i\n", ans);
  }
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

There are N bubbles in a coordinate plane. Bubbles are so tiny that it can be assumed that each bubble is a point (X_i, Y_i). 

Q Bubble Cup finalists plan to play with the bubbles. Each finalist would link to use infinitely long Bubble Cup stick to pop some bubbles. The i-th finalist would like to place the stick in the direction of vector (dxi, dyi), and plays the following game until K_i bubbles are popped. The game starts with finalist placing the stick in the direction of vector (dx_i, dy_i), and sweeping it from the infinity to the left until it hits some bubble, which is immediately popped. It is guaranteed that only one bubble will be hit in this step. After that the finalist starts rotating the stick in the counter clockwise direction with the center of rotation in point where the previous bubble was popped. When the next bubble is hit, it is immediately popped and becomes the new center of rotation. The process continues until K_i bubbles have been popped. It is guaranteed that the stick won't hit two bubbles simultaneously in this process. 

For each finalist find which bubble would be popped the last. Note that each game starts with the configuration of all N bubbles, so the games don't depend on the previous games. 

Input

The first line contains one integer N — the number of bubbles. (1 ≤ N ≤ 10^5)

Each of the next N lines contains two integers. The i-th line contains integers X_i and Y_i — the coordinates of the i-th bubble. (-10^9 ≤ X_i, Y_i ≤ 10^9, (X_i, Y_i) ≠ (X_j, Y_j) for i ≠ j)

The next line contains one integer Q — the number of finalists willing to play with the bubbles. (1 ≤ Q ≤ 10^5)

Each of the next Q lines contains 3 integers. The i-th line contains integers dx_i, dy_i and K_i. (-10^9 ≤ dx_i, dy_i ≤ 10^9, 1 ≤ K_i ≤ N)

Output

For each of the Q finalists, print the index of the bubble which would be popped last, in the separate line. 

Examples

Input


4
0 0
1 0
0 1
1 1
2
1 -1 3
-1 1 4


Output


4
2


Input


4
1 1
2 2
7 1
1 7
3
2 2 1
1 -5 4
-6 5 3


Output


3
2
3

Note

There are two finalists willing to play with the bubbles. If the first finalist plays with the bubbles, then the bubbles at coordinates (0, 0), (1, 0) and (1, 1) would be popped in that order. Their indexes are 1, 2 and 4, so the answer is 4. If the second finalist plays with the bubbles, then the bubbles at coordinates (1, 1), (0, 1), (0, 0) and (1, 0) would be popped in that order, so the answer is 2.

Visualization: [link](https://petljamediastorage.blob.core.windows.net/uploads/example1.gif). 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100050;
const int M = 2 * N;
const int L = 18;
struct vec2 {
  long long x, y;
  int idx;
  vec2() {}
  vec2(long long a, long long b) : x(a), y(b) {}
  vec2 operator-(vec2 other) const { return vec2(x - other.x, y - other.y); }
};
bool cmp(vec2 a, vec2 b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
long long cross(vec2 a, vec2 b) { return a.x * b.y - a.y * b.x; }
int part(vec2 a) { return (a.x > 0 || (a.x == 0 && a.y > 0)) ? 0 : 1; }
bool operator<(vec2 a, vec2 b) {
  int pa = part(a), push_back = part(b);
  if (pa != push_back) return pa < push_back;
  return cross(a, b) > 0;
}
struct DecrementalHull {
  int ls[M], rs[M], tsz, root;
  int ss[M], se[M];
  int ul[M], ur[M];
  int bl[M], br[M];
  int n;
  vector<vec2> pts;
  DecrementalHull() {}
  bool ccw(int i, int j, int k) {
    return cross(pts[j] - pts[i], pts[k] - pts[i]) > 0;
  }
  void pull(int c) {
    int p = ls[c], q = rs[c];
    long long sx = pts[ss[q]].x;
    while (ul[p] != ur[p] || ul[q] != ur[q]) {
      int A = ul[p], B = ur[p];
      int C = ul[q], D = ur[q];
      if (B != A && !ccw(C, B, A))
        p = ls[p];
      else if (C != D && !ccw(D, C, B))
        q = rs[q];
      else if (A == B)
        q = ls[q];
      else if (C == D)
        p = rs[p];
      else {
        long long c1 = cross(pts[B] - pts[A], pts[C] - pts[A]);
        long long c2 = cross(pts[A] - pts[B], pts[D] - pts[B]);
        if (c1 + c2 == 0 || c1 * pts[D].x + c2 * pts[C].x < sx * (c1 + c2))
          p = rs[p];
        else
          q = ls[q];
      }
    }
    ul[c] = ss[p];
    ur[c] = ss[q];
    p = ls[c], q = rs[c];
    while (bl[p] != br[p] || bl[q] != br[q]) {
      int A = bl[p], B = br[p];
      int C = bl[q], D = br[q];
      if (B != A && !ccw(A, B, C))
        p = ls[p];
      else if (C != D && !ccw(B, C, D))
        q = rs[q];
      else if (A == B)
        q = ls[q];
      else if (C == D)
        p = rs[p];
      else {
        long long c1 = cross(pts[B] - pts[A], pts[C] - pts[A]);
        long long c2 = cross(pts[A] - pts[B], pts[D] - pts[B]);
        if (c1 + c2 == 0 || c1 * pts[D].x + c2 * pts[C].x > sx * (c1 + c2))
          p = rs[p];
        else
          q = ls[q];
      }
    }
    bl[c] = ss[p];
    br[c] = ss[q];
    ss[c] = ss[ls[c]];
    se[c] = se[rs[c]];
  }
  void Build(int& c, int l, int r) {
    c = ++tsz;
    ss[c] = l;
    se[c] = r;
    if (l == r) {
      ul[c] = ur[c] = l;
      bl[c] = br[c] = l;
      return;
    }
    int mid = l + r >> 1;
    Build(ls[c], l, mid);
    Build(rs[c], mid + 1, r);
    pull(c);
  }
  void Build() {
    sort(pts.begin(), pts.end(), cmp);
    n = pts.size();
    Build(root, 0, n - 1);
  }
  void Del(int& c, int qi) {
    if (ss[c] == se[c])
      c = 0;
    else {
      if (qi <= se[ls[c]])
        Del(ls[c], qi);
      else
        Del(rs[c], qi);
      if (!ls[c])
        c = rs[c];
      else if (!rs[c])
        c = ls[c];
      else
        pull(c);
    }
  }
  vector<vec2> hull;
  vector<int> top, bot, ids;
  void GetTop(int c, int l, int r) {
    if (ul[c] == ur[c]) {
      top.push_back(ss[c]);
    } else if (ul[c] >= r) {
      GetTop(ls[c], l, r);
    } else if (ur[c] <= l) {
      GetTop(rs[c], l, r);
    } else {
      GetTop(rs[c], ur[c], r);
      GetTop(ls[c], l, ul[c]);
    }
  }
  void GetBot(int c, int l, int r) {
    if (bl[c] == br[c]) {
      bot.push_back(ss[c]);
    } else if (bl[c] >= r) {
      GetBot(ls[c], l, r);
    } else if (br[c] <= l) {
      GetBot(rs[c], l, r);
    } else {
      GetBot(ls[c], l, bl[c]);
      GetBot(rs[c], br[c], r);
    }
  }
  vector<vec2> GetHull() {
    top.clear();
    bot.clear();
    GetTop(root, 0, n - 1);
    GetBot(root, 0, n - 1);
    ids.clear();
    for (int i : bot) ids.push_back(i);
    for (int i : top)
      if (ids.back() != i && ids.front() != i) ids.push_back(i);
    hull.clear();
    for (int i : ids) hull.push_back(pts[i]);
    for (int i : ids) Del(root, i);
    return hull;
  }
} DH;
int n, q;
vec2 pts[N];
vector<vector<vec2>> layers;
vector<vec2> slopes;
vector<int> pref;
int go[N][L], idx[N];
void buildConvexHullLayers() {
  for (int i = 1; i <= n; i++) DH.pts.push_back(pts[i]);
  DH.Build();
  while (DH.root != 0) {
    vector<vec2> layer = DH.GetHull();
    for (int i = 0; i < layer.size(); i++) idx[layer[i].idx] = i;
    layers.push_back(layer);
  }
  int sz = layers[0].size();
  for (int i = 0; i < sz; i++) {
    slopes.push_back(layers[0][(i + 1) % sz] - layers[0][i]);
  }
}
void buildLayerConnections() {
  for (int i = 0; i + 1 < layers.size(); i++) {
    vector<vec2> layer = layers[i];
    vector<vec2> nextl = layers[i + 1];
    int lsz = layer.size(), ptr = 0;
    auto nxt = [&](int x) { return x + 1 == nextl.size() ? 0 : x + 1; };
    auto pre = [&](int x) { return x == 0 ? nextl.size() - 1 : x - 1; };
    for (int j = 0; j < lsz; j++) {
      vec2 src = layer[j == 0 ? lsz - 1 : j - 1];
      while (cross(nextl[ptr] - src, nextl[nxt(ptr)] - src) < 0) ptr = nxt(ptr);
      while (cross(nextl[ptr] - src, nextl[pre(ptr)] - src) < 0) ptr = pre(ptr);
      go[layer[j].idx][0] = nextl[ptr].idx;
    }
  }
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n; i++) {
      go[i][j] = go[go[i][j - 1]][j - 1];
    }
  }
  pref.reserve(layers.size() + 1);
  pref.push_back(0);
  for (int i = 0; i < layers.size(); i++) {
    pref.push_back(pref.back() + layers[i].size());
  }
}
int getFirst(vec2 dir) {
  int idx = lower_bound(slopes.begin(), slopes.end(), dir) - slopes.begin();
  if (idx == slopes.size()) idx = 0;
  return layers[0][idx].idx;
}
int getDestLayer(int k) {
  return lower_bound(pref.begin(), pref.end(), k) - pref.begin() - 1;
}
int walkCCW(int layer, int start, int steps) {
  int layer_size = layers[layer].size();
  return layers[layer][(idx[start] + steps) % layer_size].idx;
}
int main() {
  scanf("%i", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &pts[i].x, &pts[i].y);
    pts[i].idx = i;
  }
  buildConvexHullLayers();
  buildLayerConnections();
  scanf("%i", &q);
  while (q--) {
    vec2 dir;
    int k;
    scanf("%lld %lld %i", &dir.x, &dir.y, &k);
    int idx = getFirst(dir);
    int destLayer = getDestLayer(k);
    for (int j = 0; j < L; j++)
      if (destLayer >> j & 1) idx = go[idx][j];
    int ost = k - pref[destLayer];
    int ans = walkCCW(destLayer, idx, ost - 1);
    printf("%i\n", ans);
  }
  return 0;
}

```