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;
inline void pisz(int n) { printf("%d\n", n); }
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &s, vector<T> t) {
  for (int(i) = 0; (i) < (t.size()); ++(i)) s << t[i] << " ";
  return s;
}
long double eps = 1e-11;
long long a[100005];
long long b[100005];
int timenow = 0;
set<pair<int, int> > czas;
int better(int i, int j) {
  long long ci = a[i] + b[i] * timenow, cj = a[j] + b[j] * timenow;
  return ci > cj ? i : j;
}
template <class Aug>
struct ITree {
  inline static Aug plus(Aug a1, Aug a2) { return better(a1, a2); }
  static const Aug identity = 700;
  int leftend, rightend;
  Aug *state;
  ITree(int _leftend, int _rightend) : leftend(_leftend), rightend(_rightend) {
    int pot = 1;
    while (pot <= _rightend - _leftend + 5) pot <<= 1;
    pot <<= 1;
    state = new Aug[pot + 20];
    for (int(i) = 0; (i) < (pot + 20); ++(i)) state[i] = identity;
  }
  ~ITree() { delete[] state; }
  void recalc_local(int v) {
    int i = state[2 * v + 1], j = state[2 * v + 2];
    state[v] = plus(i, j);
    if (b[i] != b[j]) {
      long double spotkanie = (a[i] - a[j]) / (b[j] - b[i]);
      if (ceil(spotkanie + eps) > timenow) {
        czas.insert(make_pair((int)ceil(spotkanie + eps), v));
      }
    }
  }
  void recalc_and_up(int v) {
    recalc_local(v);
    if (v != 0) {
      int half = (v & 1) ? v / 2 : v / 2 - 1;
      recalc_and_up(half);
    }
  }
  void set_aux(int x, Aug ile, int v, int from, int to, bool justset = false) {
    if (from == to) {
      state[v] = ile;
      return;
    }
    int mid = (from + to) / 2;
    if (x <= mid)
      set_aux(x, ile, 2 * v + 1, from, mid, justset);
    else
      set_aux(x, ile, 2 * v + 2, mid + 1, to, justset);
    if (!justset) recalc_local(v);
  }
  void set(int x, Aug ile, bool justset = false) {
    set_aux(x, ile, 0, leftend, rightend, justset);
  }
  void recalc_all_aug(int v, int from, int to) {
    if (from == to) return;
    int mid = (from + to) / 2;
    recalc_all_aug(2 * v + 1, from, mid);
    recalc_all_aug(2 * v + 2, mid + 1, to);
    recalc_local(v);
  }
  void recalc_all() { recalc_all_aug(0, leftend, rightend); }
  Aug sumofaugsoverkeyssmallerorequal_aux(int x, int v, int from, int to) {
    if (x < from) return identity;
    if (from == to) return state[v];
    int mid = (from + to) / 2;
    if (x >= mid + 1)
      return plus(state[2 * v + 1], sumofaugsoverkeyssmallerorequal_aux(
                                        x, 2 * v + 2, mid + 1, to));
    return sumofaugsoverkeyssmallerorequal_aux(x, 2 * v + 1, from, mid);
  }
  Aug sumofaugsoverkeysbiggerorequal_aux(int x, int v, int from, int to) {
    if (x > to) return identity;
    if (from == to) return state[v];
    int mid = (from + to) / 2;
    if (x <= mid)
      return plus(sumofaugsoverkeysbiggerorequal_aux(x, 2 * v + 1, from, mid),
                  state[2 * v + 2]);
    return sumofaugsoverkeysbiggerorequal_aux(x, 2 * v + 2, mid + 1, to);
  }
  Aug sumofaugsoverkeyssmallerorequal(int x) {
    return sumofaugsoverkeyssmallerorequal_aux(x, 0, leftend, rightend);
  }
  Aug sumofaugsoverkeysbiggerorequal(int x) {
    return sumofaugsoverkeysbiggerorequal_aux(x, 0, leftend, rightend);
  }
  Aug sumofaugsoverkeysbetween_aux(int x, int y, int v, int from, int to) {
    if (y < from) return identity;
    if (x > to) return identity;
    if (from == to) return state[v];
    int mid = (from + to) / 2;
    if (y < mid + 1)
      return sumofaugsoverkeysbetween_aux(x, y, 2 * v + 1, from, mid);
    if (x > mid)
      return sumofaugsoverkeysbetween_aux(x, y, 2 * v + 2, mid + 1, to);
    return plus(sumofaugsoverkeysbiggerorequal_aux(x, 2 * v + 1, from, mid),
                sumofaugsoverkeyssmallerorequal_aux(y, 2 * v + 2, mid + 1, to));
  }
  Aug sumofaugsoverkeysbetween(int x, int y) {
    if (x > y) return identity;
    return sumofaugsoverkeysbetween_aux(x, y, 0, leftend, rightend);
  }
};
int ql[100005], qr[100005], qans[100005];
int main() {
  int(n), (q);
  scanf("%d %d", &(n), &(q));
  for (int(i) = 1; (i) <= (n); ++(i)) {
    int(aa), (bb);
    scanf("%d %d", &(aa), &(bb));
    a[i] = aa;
    b[i] = bb;
  }
  ITree<int> tr(1, n);
  for (int(i) = 1; (i) <= (n); ++(i)) tr.set(i, i, true);
  tr.recalc_all();
  vector<pair<int, int> > queries;
  for (int(j) = 0; (j) < (q); ++(j)) {
    int(l), (r), (t);
    scanf("%d %d %d", &(l), &(r), &(t));
    ql[j] = l;
    qr[j] = r;
    queries.push_back(make_pair(t, j));
  }
  sort(queries.begin(), queries.end());
  for (int(j) = 0; (j) < (q); ++(j)) {
    int l = ql[queries[j].second], r = qr[queries[j].second],
        t = queries[j].first;
    timenow = t;
    while (!czas.empty() && czas.begin()->first <= timenow) {
      tr.recalc_and_up(czas.begin()->second);
      czas.erase(czas.begin());
    }
    qans[queries[j].second] = tr.sumofaugsoverkeysbetween(l, r);
  }
  for (int(j) = 0; (j) < (q); ++(j)) pisz(qans[j]);
}