The races became more popular than ever at Pandora planet. But these races are quite unusual. There are $n$ cars participating in a race on the long straight track. Each car moves with a speed of $1$ meter per second. Track has coordinates in meters.

The car number $i$ moves between two points on the track with coordinates $a_i$ and $b_i$ starting at the second $0$ in the point $a_i$. The car moves from $a_i$ to $b_i$, then from $b_i$ to $a_i$, then from $a_i$ to $b_i$ again, and so on.

Handsome Mike wants to knock some cars out of the race using dynamite. Thus he has $m$ questions. The question number $j$ is: what is the number of cars in the coordinates between $x_j$ and $y_j$ inclusive after $t_j$ seconds from the start?

Your task is to answer Mike's questions.

Input Specification

The first line of the input file contains two integers $n$ and $m$ $(1\le n,m\le 1000)$ — the number of cars in the race and the number of questions.

Each of the following $n$ lines contains a description of the car: two integers $a_i$ and $b_i$ $(0\le a_i,b_i\le {10}^9,a_i\ne b_i)$ — the coordinates of the two points between which the car $i$ moves.

Each of the following $m$ lines contains a description of the question: three integers $x_j$, $y_j$, and $t_j$ $(0\le x_j\le y_j\le {10}^9,0\le t_j\le {10}^9)$ — the coordinate range and the time for the question $j$.

Output Specification

Write $m$ lines to the output file. Each line must contain one integer — the answer to the corresponding question in the order they are given in the input file.

Sample Input

5 5
0 1
0 2
2 3
3 5
4 5
0 5 0
0 1 2
0 2 1
2 5 2
2 5 3

Sample Output

5
1
2
4
3