Little R is keen on making "dark cuisine," especially mixed juices.

There are $n$ types of juice in the shop, numbered $0, 1, 2, \dots, n-1$. The deliciousness of juice $i$ is $d_i$, and its price per liter is $p_i$. When making mixed juice, Little R has some special rules: for any bottle of mixed juice, at most $l_i$ liters of juice $i$ can be added.

Now, $m$ children come to Little R asking for mixed juice. They all hope that Little R will use the juices in the shop to make a bottle of mixed juice. For the $j$-th child, they want the total price of the mixed juice to be no more than $g_j$ and the total volume to be at least $L_j$. Under these constraints, the children also want the deliciousness of the mixed juice to be as high as possible. The deliciousness of a bottle of mixed juice is defined as the minimum deliciousness among all juices participating in the mixture. Please calculate the maximum possible deliciousness of the mixed juice each child can get.

Input

The first line contains two positive integers $n$ and $m$, representing the number of juice types and the number of children.

The next $n$ lines each contain three positive integers $d_i, p_i, l_i$, representing that juice $i$ has a deliciousness of $d_i$, a price of $p_i$ per liter, and an upper limit of $l_i$ liters that can be added to a bottle.

The next $m$ lines describe all the children in order: each line contains two positive integers $g_j, L_j$ describing a child, meaning they can pay at most $g_j$ and want at least $L_j$ liters of juice.

Output

For each child, output one line containing a single integer representing the maximum deliciousness of the mixed juice they can get. If their requirements cannot be met, output $-1$.

Examples

Input 1

3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10

Output 1

3
2
-1
1

Examples 2

See juice/juice2.in and juice/juice2.ans in the contestant directory.

Examples 3

See juice/juice3.in and juice/juice3.ans in the contestant directory.

Subtasks

For all test data, it is guaranteed that $n, m \le 100000$, $1 \le d_i, p_i, l_i \le 10^5$, and $1 \le g_j, L_j \le 10^{18}$.