Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Miladin simply can’t believe how much weight he put on recently. He didn’t trust his scale, so he bought another one. Then, he didn’t trust the new one, so he bought another one. This process continued until he finally had \(N\) scales in his possession. Then, he decided he must, in an objective manner, determine whether him or the scales were correct.

He’s placed all of his scales in an array, and we say that scale which is \(i\)-th from the left has index \(i\). After that, for each scale he found out which weights it can measure. Specifically, for each \(i\), he discovered that the scale with index \(i\) can measure weights between \(d_i\) and \(u_i\), inclusive (for other weights, it outputs an error).

For his further calculations, he needs answers to \(M\) questions of the type:

Help Miladin with these calculations so he could switch to salads as soon as possible.

Input description

First line of standard input contains two integers \(N\) and \(M\) - number of scales which he collected and number of questions he needs answers to.

Line \(i\) of the next \(N\) lines contains \(2\) integers \(d_i\) and \(u_i\) - lower and upper weight bound which scale with index \(i\) can measure.

Next \(M\) lines contain three integers each \(l_i\), \(r_i\) and \(x_i\), in that order - question descriptions.

Output description

Print answers to the questions on the standard output, each in its own row, in the order they are described.

Sample 1


3 4
21 34
100 100
56 78
2 3 25
1 2 100
1 3 50
2 3 70




Sample 2


8 5
1 2
4 7
7 12
1 8
7 7
4 6
6 9
9 10
2 6 6
4 6 7
5 8 12
1 8 10
2 7 7





Test cases are divided into five disjoint groups: