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:

• For given \(l\), \(r\) and \(x\), how many scales with indices from \(l\) to \(r\) (inclusive) can measure weight \(x\)?

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

Input

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

Output

0
1
0
1

Note

• First question: No scales with indices from \(1\) to \(2\) can measure weight \(25\).
• Second question: Scale \(2\) can measure weight \(100\).
• Third question: No scales with indices from \(1\) to \(3\) can measure weight \(50\).
• Fourth question: Scale \(3\) can measure weight \(70\).

Sample 2

Input

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

Output

3
2
0
2
5

Note

• First question: between indices \(2\) and \(6\) scales with indices \(2\), \(4\) и \(6\) can measure weight \(6\).
• Second question: between indices \(4\) and \(6\) scales with indices \(4\) and \(5\) can measure weight \(7\).
• Third question: between indices \(5\) and \(8\) no scales can measure weight \(12\).
• Fourth question: between indices \(1\) and \(8\) scales with indices \(3\) and \(8\) can measure weight \(10\).
• Fifth question: between indices \(2\) and \(7\) scales with indices \(2\), \(3\), \(4\), \(5\) and \(7\) can measure weight \(7\).

Constraints

• \(1 \leq N, M \leq 2 \cdot 10^5\).
• \(0 \leq d_i \leq u_i \leq 10^9\), for \(1 \leq i \leq N\).
• \(1 \leq l_i \leq r_i \leq N\), for \(1 \leq i \leq M\).
• \(0 \leq x_i \leq 10^9\), for \(1 \leq i \leq M\).

Test cases are divided into five disjoint groups:

• In testcases worth a total of 15 points: \(N, M \leq 1000\).
• In testcases worth a total of 15 points: \(d_i = u_i\), for \(1 \leq i \leq N\).
• In testcases worth a total of 20 points: No \(x\) exists that can be measure by two different scales.
• In testcases worth a total of 20 points: \(u_i \leq 20\), for \(1 \leq i \leq N\).
• In testcases worth a total of 30 points: No additional constraints.