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 JAVA):

Solution:
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE_Iglu solver = new TaskE_Iglu();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE_Iglu {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int nQueries = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
            b[i] = in.nextInt();
        }
        IntervalTree tree = new IntervalTree(a, b);
        while (nQueries-- > 0) {
            int l = in.nextInt() - 1;
            int r = in.nextInt() - 1;
            int time = in.nextInt();
            int res = tree.query(l, r, time);
            out.println(res);
//            if (!verify(a, b, l, r, time, res)) {
//                throw new AssertionError("WA");
//            }
        }
    }

    class IntervalTree {
        int[] length;
        int[] a;
        int[] b;
        int[][] order;
        int size;

        IntervalTree(int[] a, int[] b) {
            this.a = a;
            this.b = b;
            this.size = a.length;
            int arraysSize = Math.max(1, Integer.highestOneBit(size) << 2) + 1;
            order = new int[arraysSize][];
            length = new int[arraysSize];
            initTree(0, size - 1, 1);
        }

        int query(int left, int right, long time) {
            return 1 + query(1, 0, size-1, left, right, time);
        }

        private int query(int v, int rangeLeft, int rangeRight, int left, int right, long time) {
            if (rangeLeft == left && rangeRight == right) {
                int l = 0, r = length[v]-1;
                while (l + 5 < r) {
                    int e1 = l + (r - l) / 3;
                    int e2 = e1 + (r - l) / 3;
                    if (compare(time, order[v][e1], order[v][e2])) {
                        r = e2;
                    } else {
                        l = e1;
                    }
                }
                int res = order[v][l];
                for (int i = l + 1; i <= r; ++i) {
                    if (compare(time, order[v][i], res)) {
                        res = order[v][i];
                    }
                }
                return res;
            }
            int middle = (rangeLeft + rangeRight) / 2;
            int l = -1, r = -1;
            if (left <= middle) {
                l = query(v * 2, rangeLeft, middle, left, Math.min(right, middle), time);
            }
            if (right > middle) {
                r = query(v * 2 + 1, middle + 1, rangeRight, Math.max(left, middle + 1), right, time);
            }
            if (l == -1 && r == -1) return -1;
            if (l == -1) return r;
            if (r == -1) return l;
            if (compare(time, l, r)) {
                return l;
            }
            return r;
        }

        boolean compare(long time, int leftIndex, int rightIndex) {
            return a[leftIndex] + b[leftIndex] * time > a[rightIndex] + b[rightIndex] * time;
        }

        private void initTree(int left, int right, int v) {
            if (right != left) {
                int middle = (left + right) / 2;
                initTree(left, middle, 2 * v);
                initTree(middle + 1, right, 2 * v + 1);
                order[v] = new int[length[2 * v] + length[2 * v + 1]];

                int pointer1 = 0;
                int pointer2 = 0;

                while (pointer1 < length[2 * v] || pointer2 < length[2 * v + 1]) {
                    int candidate;
                    if (pointer1 < length[2 * v] && ((pointer2 >= length[2 * v + 1]) ||
                            b[order[2 * v][pointer1]] < b[order[2 * v + 1][pointer2]] ||
                            (b[order[2 * v][pointer1]] == b[order[2 * v + 1][pointer2]] &&
                                    a[order[2 * v][pointer1]] < a[order[2 * v + 1][pointer2]]))) {
                        candidate = order[2 * v][pointer1++];
                    } else {
                        candidate = order[2 * v + 1][pointer2++];
                    }
                    if (length[v] == 0) {
                        order[v][length[v]++] = candidate;
                    } else {
                        while (length[v] > 1) {
                            if (b[order[v][length[v]-1]] == b[candidate]) {
                                --length[v];
                                continue;
                            }
                            Rational t1 = new Rational(
                                a[order[v][length[v]-2]] - a[order[v][length[v]-1]],
                                -b[order[v][length[v]-2]] + b[order[v][length[v]-1]]);
                            Rational t2 = new Rational(
                                a[order[v][length[v]-1]] - a[candidate],
                                -b[order[v][length[v]-1]] + b[candidate]);
                            if (t1.compareTo(t2) >= 0) {
                                --length[v];
                            } else {
                                break;
                            }
                        }
                        if (b[order[v][length[v]-1]] == b[candidate]) {
                            --length[v];
                        }
                        order[v][length[v]++] = candidate;
                    }

                }

            } else {
                order[v] = new int[1];
                order[v][0] = left;
                length[v] = 1;
            }
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class Rational implements Comparable<Rational> {
    long num;
    long denom;

    public Rational(long num, long denom) {
        this.num = num;
        this.denom = denom;
        if (this.denom == 0) {
            throw new IllegalArgumentException("Denom == 0!");
        }
        long gcd = Math.abs(IntegerUtils.gcd(this.num, this.denom));
        if (this.denom > 0) {
            this.num /= gcd;
            this.denom /= gcd;
        } else {
            this.num = -this.num / gcd;
            this.denom = -this.denom / gcd;
        }
    }

    public String toString() {
        StringBuilder b = new StringBuilder("");
        b.append(num).append("/").append(denom);
        return b.toString();
    }


    public int compareTo(Rational o) {
        return IntegerUtils.longCompare(num * o.denom, denom * o.num);
    }
}

class IntegerUtils {

    public static long gcd(long x, long y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    public static int longCompare(long a, long b) {
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    }

}