21949번 - Cambridge 다국어

The admission interview at the prestigious University of Cambridge consist of N tasks, numbered from 1 to N. Alex is there right now, waiting to attend the interview. Takahiro Wong, who has just finished his interview, solved all the tasks. More precisely, he solved the i-th problem after Di seconds from the beginning of the interview.

Knowing the fact that he can solve the i-th problem in T_i seconds, Alex asks himself M questions: x y. For every question, Alex will consider only the tasks from the interval [x;y] and he wants to know whether he can solve each of these tasks before Takahiro Wong. (Alex can solve the tasks from the interval [x;y] in any order).

For example, let’s consider that Alex has to solve the tasks a and b (in this order). He will finish task a after T_a seconds, and task b after T_a + T_b seconds. Alex will solve both problems before Takahiro Wong if T_a < D_a and T_a + T_b < D_b.

Both Takahiro Wong and Alex will start their interviews at second 0.

Help Alex answer correctly to all M questions.

• The first line of the standard input will contain N and M.
  • N - the number of tasks, M - the number of questions.
• On the following N lines, there will be T_i and D_i.
  • T_i - the time needed for Alex to solve the i-th problem
  • D_i - the time (from the beginning of his interview) after Takahiro Wong will solve the i-th problem.
• On the following M lines, there will be x and y, representing the interval [x;y]

The standard output will contain M lines, the answers to the M questions.

The i-th line will contain:

• 1, if Alex cand solve all the tasks from the interval [x;y] before Takahiro Wond
• 0, otherwise.

• 1 ≤ N, M ≤ 10⁵
• 1 ≤ T_i < D_i ≤ 10⁹
• The D_i values are not distinct (there can be a value that appears multiple times)
• Alex can’t solve 2 tasks in the same time, but Takahiro Wong can (The Divalues are not distinct).

The 3rd question refers to the interval [1;3]:

• There are 6 ways Alex can solve the tasks: (1,2,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).
• If he solves the tasks in the order (1, 3, 2), we have to fulfill the following relations: T₁ < D₁, T₁ + T₃ < D₃ and T₁ + T₃ + T₂ < D₂. We can see that all of them are true.
• Because Alex found at least one way to solve all the problems before Takahiro Wong, the answer is 1 for the third question.