Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Stick Race

By mainstring · Limits 1s, 512 MB

It is the annual sports event in your school. There is an event going on named ‘‘Stick Race’’.

This is basically a race between multiple groups of students. In each group, there are one or multiple students who work as a team. One student starts the race with a stick in their hand; runs some distance, and passes the stick to another student from their group. Then the second student runs some distance with the stick and passes it to the third person of their group. The race goes on like this and it ends when a student crosses the finishing line with the stick.

The event contains RR number of races. Each race has a race track that is a straight line. The iith track starts from point AiA_i and ends in point BiB_i.

For each race, you can form separate groups. There are MM students available to form your groups. You can use one student in multiple races. But for each race, you can use one student only once.

Each student has the following limitations:

  • Student ii does not have the stamina to run more than SiS_i distance.

  • Student ii lives at point XiX_i aligned with the race track line. And their parents want them to start their run from home.

Your task is to build one team per race, with the least number of students who can complete the race.

The data set will be given in such way that you can build at least one team per race to complete the race.

Input

The first line of input will contain 2 numbers, MM and RR.
Each of next MM line will contain 2 numbers, XiX_i and SiS_i.
Each of next RR line will contain 2 numbers, AiA_i and BiB_i.

AiA_i will always be the starting point of at least one student.

Constraints

Subtask 1 (10 Points)

1<=M<=1000001 <= M <= 100000

1<=R<=101 <= R <= 10

0<=Xi<=1000000 <= X_i <= 100000

1<=Si<=1000001 <= S_i <= 100000

0<=Ai<Bi<=1000000 <= A_i < B_i <= 100000

SiS_i will be equal for all students.

Subtask 2 (40 Points)

1<=M<=1000001 <= M <= 100000

1<=R<=101 <= R <= 10

0<=Xi<=1000000 <= X_i <= 100000

1<=Si<=1000001 <= S_i <= 100000

0<=Ai<Bi<=1000000 <= A_i < B_i <= 100000

Subtask 3 (50 Points)

1<=M<=1000001 <= M <= 100000

1<=R<=1000001 <= R <= 100000

0<=Xi<=1000000 <= X_i <= 100000

1<=Si<=1000001 <= S_i <= 100000

0<=Ai<Bi<=1000000 <= A_i < B_i <= 100000

Output

Print RR lines; the iith line containing the minimum number of students required to complete the iith race.

Sample

InputOutput
6 2
5 4
8 4
3 4
7 4
10 4
9 4
5 14
3 10
3
2

For the first race, it is 5 -> 9, 9 -> 10, 10 -> 14
The student who lives in 5, goes to point 9, gives to stick to the student who lives in 9. Then that student runs to point 10 and gives the stick to another student who then runs to point 14 to finish the race.

For the second race, 3 -> 7, 7 -> 10


    Discussion

    Statistics


    80% Solution Ratio

    Um_nikEarliest, 1M ago

    gryffindoFastest, 0.1s

    Deshi_TouristLightest, 21 MB

    Deshi_TouristShortest, 2364B

    Submit

    Login to submit

    Editorial

    This problem can be solved using sparse table and segment tree. Let's assume, there is student A who...