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.util.InputMismatchException;
import java.math.BigInteger;
import java.util.Collection;
import java.util.ArrayList;
import java.util.List;
import java.io.*;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Arrays;

/**
 * Generated by Contest helper plug-in
 * Actual solution is at the bottom
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new StreamInputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		run(in, out);
	}

	public static void run(InputReader in, PrintWriter out) {
		Solver solver = new TaskE();
		solver.solve(1, in, out);
		Exit.exit(in, out);
	}
}

abstract class InputReader {
	private boolean finished = false;

	public abstract int read();

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuffer res = new StringBuffer();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public void setFinished(boolean finished) {
		this.finished = finished;
	}

	public abstract void close();
}

class StreamInputReader extends InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar, numChars;

	public StreamInputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public void close() {
		try {
			stream.close();
		} catch (IOException ignored) {
		}
	}
}

class Exit {
	private Exit() {
	}

	public static void exit(InputReader in, PrintWriter out) {
		in.setFinished(true);
		in.close();
		out.close();
	}
}

interface Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out);
}

class IOUtils {

	public static void readIntArrays(InputReader in, int[]... arrays) {
		for (int i = 0; i < arrays[0].length; i++) {
			for (int j = 0; j < arrays.length; j++)
				arrays[j][i] = in.readInt();
		}
	}

	}

class IntegerUtils {
	public static long gcd(long a, long b) {
		while (b != 0) {
			long temp = a % b;
			a = b;
			b = temp;
		}
		return a;
	}

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

	}

class Rational implements Comparable<Rational> {
	private final long numerator;
	private final long denominator;
	;

	public Rational(long numerator, long denominator) {
		if (denominator == 0)
			throw new IllegalArgumentException();
		long gcd = IntegerUtils.gcd(Math.abs(numerator), Math.abs(denominator));
		if (denominator > 0) {
			this.numerator = numerator / gcd;
			this.denominator = denominator / gcd;
		} else {
			this.numerator = -numerator / gcd;
			this.denominator = -denominator / gcd;
		}
	}

	public String toString() {
		return numerator + "/" + denominator;
	}

	public int compareTo(Rational other) {
		return IntegerUtils.longCompare(numerator * other.denominator, denominator * other.numerator);
	}
}

class TaskE implements Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
		int walrusCount = in.readInt();
		int queryCount = in.readInt();
		int[] initial = new int[walrusCount];
		int[] perTurn = new int[walrusCount];
		IOUtils.readIntArrays(in, initial, perTurn);
		IntervalTree tree = new IntervalTree(initial, perTurn);
		for (int i = 0; i < queryCount; i++) {
			int left = in.readInt() - 1;
			int right = in.readInt();
			int time = in.readInt();
			out.println(tree.query(left, right, time) + 1);
		}
	}
}

class IntervalTree {
	private int[] left;
	private int[] right;
	private int[][] order;
	private int[] length;
	private final int[] initial;
	private final int[] perTurn;

	public IntervalTree(int[] initial, int[] perTurn) {
		this.initial = initial;
		this.perTurn = perTurn;
		int size = initial.length;
		int arraysSize = Math.max(1, Integer.highestOneBit(size) << 2);
		left = new int[arraysSize];
		right = new int[arraysSize];
		order = new int[arraysSize][];
		length = new int[arraysSize];
		initTree(0, size, 0);
	}

	private void initTree(int left, int right, int root) {
		this.left[root] = left;
		this.right[root] = right;
		if (right - left > 1) {
			initTree(left, (left + right + 1) / 2, 2 * root + 1);
			initTree((left + right + 1) / 2, right, 2 * root + 2);
			int index1 = 0;
			int index2 = 0;
			order[root] = new int[length[2 * root + 1] + length[2 * root + 2]];
			while (index1 < length[2 * root + 1] || index2 < length[2 * root + 2]) {
				int candidate;
				if (index1 < length[2 * root + 1] && (index2 == length[2 * root + 2] ||
					initial[order[2 * root + 1][index1]] > initial[order[2 * root + 2][index2]] ||
					initial[order[2 * root + 1][index1]] == initial[order[2 * root + 2][index2]] &&
					perTurn[order[2 * root + 1][index1]] > perTurn[order[2 * root + 2][index2]]))
				{
					candidate = order[2 * root + 1][index1++];
				} else
					candidate = order[2 * root + 2][index2++];
				if (length[root] == 0 || perTurn[candidate] > perTurn[order[root][length[root] - 1]]) {
					while (length[root] > 1) {
						Rational time1 = new Rational(initial[order[root][length[root] - 2]] - initial[order[root][length[root] - 1]],
							-perTurn[order[root][length[root] - 2]] + perTurn[order[root][length[root] - 1]]);
						Rational time2 = new Rational(initial[candidate] - initial[order[root][length[root] - 1]],
							-perTurn[candidate] + perTurn[order[root][length[root] - 1]]);
						if (time1.compareTo(time2) >= 0)
							length[root]--;
						else
							break;
					}
					order[root][length[root]++] = candidate;
				}
			}
		} else {
			order[root] = new int[1];
			order[root][0] = left;
			length[root] = 1;
		}
	}

	public int query(int left, int right, long time) {
		return query(left, right, time, 0);
	}

	private int query(int left, int right, long time, int root) {
		if (this.left[root] >= right || this.right[root] <= left)
			return -1;
		if (this.left[root] >= left && this.right[root] <= right) {
			int leftIndex = 0;
			int rightIndex = length[root] - 1;
			while (rightIndex > leftIndex + 2) {
				int leftMiddle = (2 * leftIndex + rightIndex) / 3;
				int rightMiddle = (2 * rightIndex + leftIndex) / 3;
				if (compare(time, order[root][leftMiddle], order[root][rightMiddle]))
					rightIndex = rightMiddle;
				else
					leftIndex = leftMiddle;
			}
			int result = order[root][leftIndex];
			for (int i = leftIndex + 1; i <= rightIndex; i++) {
				if (compare(time, order[root][i], result))
					result = order[root][i];
			}
			return result;
		}
		int leftIndex = query(left, right, time, 2 * root + 1);
		int rightIndex = query(left, right, time, 2 * root + 2);
		if (leftIndex == -1)
			return rightIndex;
		if (rightIndex == -1)
			return leftIndex;
		if (compare(time, leftIndex, rightIndex))
			return leftIndex;
		return rightIndex;
	}

	private boolean compare(long time, int leftIndex, int rightIndex) {
		return initial[leftIndex] + perTurn[leftIndex] * time > initial[rightIndex] + perTurn[rightIndex] * time;
	}
}