Problem: Today the North Pole hosts an Olympiad in a sport called... toy igloo skyscrapers' building!

There are n walruses taking part in the contest. Each walrus is given a unique number from 1 to n. After start each walrus begins to build his own igloo skyscraper. Initially, at the moment of time equal to 0, the height of the skyscraper i-th walrus is equal to ai. Each minute the i-th walrus finishes building bi floors.

The journalists that are reporting from the spot where the Olympiad is taking place, make q queries to the organizers. Each query is characterized by a group of three numbers li, ri, ti. The organizers respond to each query with a number x, such that:

1. Number x lies on the interval from li to ri inclusive (li ≤ x ≤ ri).

2. The skyscraper of the walrus number x possesses the maximum height among the skyscrapers of all walruses from the interval [li, ri] at the moment of time ti.

For each journalists' query print the number of the walrus x that meets the above-given criteria. If there are several possible answers, print any of them.

Input

The first line contains numbers n and q (1 ≤ n, q ≤ 105). Next n lines contain pairs of numbers ai, bi (1 ≤ ai, bi ≤ 109). Then follow q queries i the following format li, ri, ti, one per each line (1 ≤ li ≤ ri ≤ n, 0 ≤ ti ≤ 106). All input numbers are integers.

Output

For each journalists' query print the number of the walrus x that meets the criteria, given in the statement. Print one number per line.

Examples

Input

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


Output

5
2
1
5


Input

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


Output

3
3
3
1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 20;
struct line {
  long long a, b, idx;
  line(long long a1 = 0, long long a2 = 0, long long a3 = 0)
      : a(a1), b(a2), idx(a3) {}
  void print() { printf("idx = %lld, a = %lld, b = %lld\n", idx, a, b); }
};
struct que {
  int l, r, t, idx;
  que(int a = 0, int b = 0, int c = 0, int d = 0) : l(a), r(b), t(c), idx(d) {}
};
line ls[MAX];
que qs[MAX];
long long ans[MAX];
vector<line> l[MAX];
int curid[MAX];
int sz, n, q, tsz;
int getid(int i) {
  i++;
  if (i % sz == 0)
    return i / sz - 1;
  else
    return i / sz;
}
bool check(const line &cur, const line &prev, const line &pi) {
  return (prev.a - cur.a) * cur.b + (cur.b - prev.b) * cur.a <=
         pi.b * (prev.a - cur.a) + pi.a * (cur.b - prev.b);
}
bool check2(const line &prev, const line &nxt, long long t) {
  if (prev.b > nxt.b)
    return nxt.a - prev.a <= (prev.b - nxt.b) * t;
  else
    return nxt.a - prev.a >= (prev.b - nxt.b) * t;
}
void calL() {
  for (int i = 0; i < tsz; i++) {
    vector<line> tmp, ans;
    int s = i * sz, e = min((i + 1) * sz - 1, n - 1);
    for (int j = s; j <= e; j++) {
      tmp.push_back(ls[j]);
    }
    sort(tmp.begin(), tmp.end(), [](const line &a, const line &b) {
      if (a.b != b.b)
        return a.b < b.b;
      else
        return a.a > b.a;
    });
    s = 0;
    while (s < tmp.size()) {
      if (ans.size() == 0)
        ans.push_back(tmp[s]);
      else {
        while (ans.size() > 1) {
          int cid = ans.size() - 1;
          if (check(ans[cid], ans[cid - 1], tmp[s]))
            ans.pop_back();
          else
            break;
        }
        if (ans.size() == 1) {
          if (ans[0].a <= tmp[s].a) ans.pop_back();
        }
        ans.push_back(tmp[s]);
      }
      int j = s + 1;
      while (j < tmp.size() && tmp[j].b == tmp[s].b) j++;
      s = j;
    }
    l[i] = move(ans);
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    ls[i] = {a, b, i};
  }
  sz = 1;
  while (sz * sz <= n) sz++;
  sz--;
  if (n % sz == 0)
    tsz = n / sz;
  else
    tsz = n / sz + 1;
  for (int i = 0; i < q; i++) {
    int l, r, t;
    scanf("%d%d%d", &l, &r, &t);
    qs[i] = {l - 1, r - 1, t, i};
  }
  sort(qs, qs + q, [](const que &a, const que &b) { return a.t < b.t; });
  memset(curid, 0, sizeof(curid));
  calL();
  for (int i = 0; i < q; i++) {
    que &nn = qs[i];
    bool debug = 0;
    int ct = nn.t;
    if (debug) printf("ct = %d\n", ct);
    for (int j = 0; j < tsz; j++) {
      if (curid[j] == (int)l[j].size() - 1) continue;
      while (curid[j] + 1 < l[j].size()) {
        int cur = curid[j], nxt = curid[j] + 1;
        if (check2(l[j][cur], l[j][nxt], nn.t))
          curid[j]++;
        else
          break;
      }
    }
    int b1 = getid(nn.l), b2 = getid(nn.r);
    assert(b1 >= 0 && b1 < tsz);
    assert(b2 >= 0 && b2 < tsz);
    if (b1 == b2) {
      int midx;
      long long opt = LLONG_MIN;
      for (int j = nn.l; j <= nn.r; j++) {
        long long tmp = ls[j].a + ls[j].b * ct;
        if (tmp > opt) opt = tmp, midx = ls[j].idx;
      }
      ans[nn.idx] = midx;
    } else {
      if (debug) {
        printf("hh id = %d\n", i);
        for (int j = 0; j < tsz; j++) {
          printf("id = %d\n", j);
          for (int k = 0; k < l[j].size(); k++) {
            l[j][k].print();
            if (k + 1 < l[j].size())
              printf("%lf\n", double(l[j][k + 1].a - l[j][k].a) /
                                  (l[j][k].b - l[j][k + 1].b));
          }
          printf("curid = %d\n", curid[j]);
          printf("\n");
        }
      }
      int midx;
      long long opt = LLONG_MIN;
      int tb = (b1 + 1) * sz - 1;
      for (int j = nn.l; j <= tb; j++) {
        long long tmp = ls[j].a + ls[j].b * ct;
        if (tmp > opt) opt = tmp, midx = ls[j].idx;
      }
      tb = b2 * sz;
      for (int j = tb; j <= nn.r; j++) {
        long long tmp = ls[j].a + ls[j].b * ct;
        if (tmp > opt) opt = tmp, midx = ls[j].idx;
      }
      for (int bidx = b1 + 1; bidx < b2; bidx++) {
        const line &cl = l[bidx][curid[bidx]];
        long long tmp = cl.a + cl.b * ct;
        if (tmp > opt) opt = tmp, midx = cl.idx;
      }
      ans[nn.idx] = midx;
    }
  }
  for (int i = 0; i < q; i++) printf("%lld\n", ans[i] + 1);
  return 0;
}