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;
template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <class T>
void pvp(T a, T b) {
  for (T i = a; i != b; ++i)
    cout << "(" << i->first << ", " << i->second << ") ";
  cout << endl;
}
template <class T>
void chmin(T &t, T f) {
  if (t > f) t = f;
}
template <class T>
void chmax(T &t, T f) {
  if (t < f) t = f;
}
int in_c() {
  int c;
  for (; (c = getchar()) <= ' ';) {
    if (!~c) throw ~0;
  }
  return c;
}
int in() {
  int x = 0, c;
  for (; (unsigned)((c = getchar()) - '0') >= 10;) {
    if (c == '-') return -in();
    if (!~c) throw ~0;
  }
  do {
    x = (x << 3) + (x << 1) + (c - '0');
  } while ((unsigned)((c = getchar()) - '0') < 10);
  return x;
}
long long In() {
  long long x = 0, c;
  for (; (unsigned)((c = getchar()) - '0') >= 10;) {
    if (c == '-') return -In();
    if (!~c) throw ~0;
  }
  do {
    x = (x << 3) + (x << 1) + (c - '0');
  } while ((unsigned)((c = getchar()) - '0') < 10);
  return x;
}
const double INF = 1e+10;
int N, Q;
int A[400010], B[400010];
int QL[400010], QR[400010], QT[400010];
int segn;
int segLen[400010];
double *segT[400010];
int *segI[400010];
int len, len01, LEN;
double ts[400010], ts01[400010], TS[400010];
int is[400010], is0[400010], is1[400010], IS[400010];
void segMerge(int u, int v0, int v1) {
  int x, x0, x1, xx;
  int i0, i1;
  double t, tt;
  len01 = 0;
  ts01[0] = 0.0;
  for (x0 = x1 = 0; segT[v0][x0] < INF && segT[v1][x1] < INF;) {
    is0[len01] = segI[v0][x0];
    is1[len01] = segI[v1][x1];
    if (segT[v0][x0 + 1] <= segT[v1][x1 + 1]) {
      ts01[++len01] = segT[v0][++x0];
    } else {
      ts01[++len01] = segT[v1][++x1];
    }
  }
  len = 0;
  ts[0] = 0.0;
  for (x = 0; x < len01; ++x) {
    i0 = is0[x];
    i1 = is1[x];
    if (B[i0] != B[i1]) {
      t = -(A[i0] - A[i1]) / (double)(B[i0] - B[i1]);
      if (ts01[x] < t && t < ts01[x + 1]) {
        tt = (ts01[x] + t) / 2.0;
        is[len] = (A[i0] + B[i0] * tt >= A[i1] + B[i1] * tt) ? i0 : i1;
        ts[++len] = t;
        tt = (t + ts01[x + 1]) / 2.0;
        is[len] = (A[i0] + B[i0] * tt >= A[i1] + B[i1] * tt) ? i0 : i1;
        ts[++len] = ts01[x + 1];
        continue;
      }
    }
    tt = (ts01[x] + ts01[x + 1]) / 2.0;
    is[len] = (A[i0] + B[i0] * tt >= A[i1] + B[i1] * tt) ? i0 : i1;
    ts[++len] = ts01[x + 1];
  }
  LEN = 0;
  TS[0] = 0.0;
  for (x = 0; x < len; x = xx) {
    for (xx = x; xx < len && is[x] == is[xx]; ++xx)
      ;
    IS[LEN] = is[x];
    TS[++LEN] = ts[xx];
  }
  segLen[u] = LEN;
  segT[u] = new double[LEN + 1];
  segI[u] = new int[LEN];
  memcpy(segT[u], TS, sizeof(double) * (LEN + 1));
  memcpy(segI[u], IS, sizeof(int) * LEN);
}
int segMaxIndex(int a, int b, double t) {
  double dai = 0.0, tmp;
  int im = N, i;
  a += segn;
  b += segn;
  for (; a <= b; a >>= 1, b >>= 1) {
    if (a & 1) {
      i = segI[a][upper_bound(segT[a], segT[a] + segLen[a], t) - segT[a] - 1];
      tmp = A[i] + B[i] * t;
      if (dai < tmp) {
        dai = tmp;
        im = i;
      }
      ++a;
    }
    if (~b & 1) {
      i = segI[b][upper_bound(segT[b], segT[b] + segLen[b], t) - segT[b] - 1];
      tmp = A[i] + B[i] * t;
      if (dai < tmp) {
        dai = tmp;
        im = i;
      }
      --b;
    }
  }
  return im;
}
int main() {
  int q;
  int i;
  int u;
  for (; ~scanf("%d%d", &N, &Q);) {
    for (i = 0; i < N; ++i) {
      A[i] = in();
      B[i] = in();
    }
    A[N] = B[N] = 0;
    for (q = 0; q < Q; ++q) {
      QL[q] = in() - 1;
      QR[q] = in() - 1;
      QT[q] = in();
    }
    for (segn = 1; segn < N; segn <<= 1)
      ;
    for (i = 0; i < segn; ++i) {
      u = segn + i;
      segLen[u] = 1;
      segT[u] = new double[2];
      segI[u] = new int[1];
      segT[u][0] = 0.0;
      segT[u][1] = INF;
      segI[u][0] = min(i, N);
    }
    for (u = segn; --u;) {
      segMerge(u, u << 1 | 0, u << 1 | 1);
    }
    for (q = 0; q < Q; ++q) {
      i = segMaxIndex(QL[q], QR[q], QT[q]);
      printf("%d\n", i + 1);
    }
    for (u = 0; u < segn << 1; ++u) {
      delete[] segT[u];
      delete[] segI[u];
    }
  }
  return 0;
}