ICPC NEERC 2014 K - Knockout Racing

View as PDF

Submit solution


Points: 7
Time limit: 3.0s
Memory limit: 1G

Problem type

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

Comments

There are no comments at the moment.