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>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkmax(T &a, T b) {
  if (b > a) a = b;
}
int cond = (long long)1;
int n;
const int sz = (1 << 17);
vector<pair<pair<int, int>, int> > zb[sz * 2];
vector<long double> qt[sz * 2];
vector<pair<pair<int, int>, int> > qpkt[sz * 2];
vector<int> dimone(int p) {
  vector<int> ret;
  p += sz;
  while (p >= 1) {
    ret.push_back(p);
    p /= 2;
  }
  return ret;
}
vector<int> dimtwo(int p1, int p2) {
  vector<int> ret;
  p1 += sz;
  p2 += sz;
  ret.push_back(p1);
  if (p1 != p2) ret.push_back(p2);
  while (p1 != p2 && ((p1 ^ 1) != p2)) {
    if (p1 < (p1 ^ 1)) ret.push_back(p1 ^ 1);
    if ((p2 ^ 1) < p2) ret.push_back(p2 ^ 1);
    p1 /= 2;
    p2 /= 2;
  }
  return ret;
}
void _main() {
  int n, q;
  scanf("%d%d", &n, &q);
  {
    if (cond > 0) {
      cond--;
      for (int xxx = (0); xxx < (1); ++xxx)
        cerr << 84 << " "
             << "n"
             << " " << n << endl;
      cerr.flush();
    }
  };
  for (int i = (0); i < (n); ++i) {
    vector<int> where = dimone(i);
    int a, b;
    scanf("%d%d", &a, &b);
    for (__typeof((where).begin()) it = (where).begin(); it != (where).end();
         ++it) {
      {
        if (cond > 0) {
          cond--;
          for (int xxx = (0); xxx < (1); ++xxx)
            cerr << 90 << " "
                 << "i << \" \" << *it"
                 << " " << i << " " << *it << endl;
          cerr.flush();
        }
      };
      zb[*it].push_back(make_pair(make_pair(a, b), i));
    }
  }
  for (int i = (0); i < (2 * sz); ++i)
    if (zb[i].size()) {
      sort((zb[i]).begin(), (zb[i]).end());
      reverse((zb[i]).begin(), (zb[i]).end());
      qt[i].push_back(0);
      qpkt[i].push_back(zb[i][0]);
      for (int j = (1); j <= ((int)zb[i].size() - 1); ++j) {
        pair<pair<int, int>, int> cur = zb[i][j];
        if (cur.first.first < qpkt[i].back().first.first &&
            cur.first.second > qpkt[i].back().first.second) {
          {
            if (cond > 0) {
              cond--;
              for (int xxx = (0); xxx < (1); ++xxx)
                cerr << 102 << " "
                     << "cur.x.x << \" \" << cur.x.y"
                     << " " << cur.first.first << " " << cur.first.second
                     << endl;
              cerr.flush();
            }
          };
          {
            if (cond > 0) {
              cond--;
              for (int xxx = (0); xxx < (1); ++xxx)
                cerr << 103 << " "
                     << "\"\""
                     << " "
                     << "" << endl;
              cerr.flush();
            }
          };
          while (true) {
            {
              if (cond > 0) {
                cond--;
                for (int xxx = (0); xxx < (1); ++xxx)
                  cerr << 106 << " "
                       << "cur.x.x << \" \" << cur.x.y << \" \" << "
                          "qpkt[i].back().x.x << \" \" << qpkt[i].back().x.y"
                       << " " << cur.first.first << " " << cur.first.second
                       << " " << qpkt[i].back().first.first << " "
                       << qpkt[i].back().first.second << endl;
                cerr.flush();
              }
            };
            long double t =
                (long double)(qpkt[i].back().first.first - cur.first.first) /
                (cur.first.second - qpkt[i].back().first.second);
            assert(t >= 0);
            if (t <= qt[i].back() && qpkt[i].size() >= 2) {
              qt[i].pop_back();
              qpkt[i].pop_back();
            } else {
              qt[i].push_back(t);
              qpkt[i].push_back(cur);
              break;
            }
          }
          {
            if (cond > 0) {
              cond--;
              for (int xxx = (0); xxx < (1); ++xxx)
                cerr << 119 << " "
                     << "\"\""
                     << " "
                     << "" << endl;
              cerr.flush();
            }
          };
        }
      }
      {
        if (cond > 0) {
          cond--;
          for (int xxx = (0); xxx < (1); ++xxx)
            cerr << 122 << " "
                 << "\"\""
                 << " "
                 << "" << endl;
          cerr.flush();
        }
      };
    }
  for (int iii = (0); iii < (q); ++iii) {
    int a, b;
    int t;
    scanf("%d%d%d", &a, &b, &t);
    a--;
    b--;
    {
      if (cond > 0) {
        cond--;
        for (int xxx = (0); xxx < (1); ++xxx)
          cerr << 130 << " "
               << "\"\""
               << " "
               << "" << endl;
        cerr.flush();
      }
    };
    vector<int> where = dimtwo(a, b);
    {
      if (cond > 0) {
        cond--;
        for (int xxx = (0); xxx < (1); ++xxx)
          cerr << 132 << " "
               << "\"\""
               << " "
               << "" << endl;
        cerr.flush();
      }
    };
    int best = -2;
    long long bval = -1;
    {
      if (cond > 0) {
        cond--;
        for (int xxx = (0); xxx < (1); ++xxx)
          cerr << 135 << " "
               << "a << \" \" << b << \" \" << t"
               << " " << a << " " << b << " " << t << endl;
        cerr.flush();
      }
    };
    for (__typeof((where).begin()) it = (where).begin(); it != (where).end();
         ++it)
      if (qt[*it].size()) {
        int i = *it;
        {
          if (cond > 0) {
            cond--;
            for (int xxx = (0); xxx < (1); ++xxx)
              cerr << 138 << " "
                   << "iii << \" \" << i"
                   << " " << iii << " " << i << endl;
            cerr.flush();
          }
        };
        if (cond) {
          for (__typeof((qt[i]).begin()) it = (qt[i]).begin();
               it != (qt[i]).end(); ++it)
            cerr << *it << " ";
          cerr << endl;
          for (__typeof((qpkt[i]).begin()) it = (qpkt[i]).begin();
               it != (qpkt[i]).end(); ++it)
            cerr << it->first.first << " " << it->first.second << "  ";
          cerr << endl;
        }
        int p = lower_bound(qt[i].begin(), qt[i].end(), (long double)t) -
                qt[i].begin();
        if (p) p--;
        {
          if (cond > 0) {
            cond--;
            for (int xxx = (0); xxx < (1); ++xxx)
              cerr << 147 << " "
                   << "t << \" \" << qt[i][0]"
                   << " " << t << " " << qt[i][0] << endl;
            cerr.flush();
          }
        };
        pair<pair<int, int>, int> cand = qpkt[i][p];
        long long cval = cand.first.first + (long long)cand.first.second * t;
        {
          if (cond > 0) {
            cond--;
            for (int xxx = (0); xxx < (1); ++xxx)
              cerr << 150 << " "
                   << "cval << \" \" << cand.y << \" \" << t"
                   << " " << cval << " " << cand.second << " " << t << endl;
            cerr.flush();
          }
        };
        if (bval < cval) {
          bval = cval;
          best = cand.second;
        }
      }
    printf("%d\n", best + 1);
  }
}
int main(int argc, char **argv) {
  string p = "../gcj/source/" + string("") + argv[0][strlen(argv[0]) - 1];
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "1n") == 0) {
      freopen("1.in", "r", stdin);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "2n") == 0) {
      freopen("2.in", "r", stdin);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "3n") == 0) {
      freopen("3.in", "r", stdin);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "4n") == 0) {
      freopen("4.in", "r", stdin);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "5n") == 0) {
      freopen("5.in", "r", stdin);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "s0") == 0) {
      freopen((p + "-small-0.in").c_str(), "r", stdin);
      freopen((p + "-small-0.out").c_str(), "w", stdout);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "s1") == 0) {
      freopen((p + "-small-1.in").c_str(), "r", stdin);
      freopen((p + "-small-1.out").c_str(), "w", stdout);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "s2") == 0) {
      freopen((p + "-small-2.in").c_str(), "r", stdin);
      freopen((p + "-small-2.out").c_str(), "w", stdout);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "l0") == 0) {
      freopen((p + "-large-0.in").c_str(), "r", stdin);
      freopen((p + "-large-0.out").c_str(), "w", stdout);
    }
  for (int i = (0); i < (argc); ++i)
    if (strcmp(argv[i], "q") == 0) cond = 1 << 30;
  cerr << sz << endl;
  _main();
  return 0;
}