Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Hiring

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThe head of human resources department decided to hire a new employee. He created a test exercise for candidates which should be accomplished in at most *m* working days. Each candidate has to pass this test exercise. During the *j*-th day a candidate is allowed to be in the office for at most *t*_{j} units of time.

Overall, *n* candidates decided to apply for the job and sent out their resumes. Based on data received the head has defined two parameters describing every candidate: *d*_{i} and *r*_{i}. The parameter *d*_{i} is the time to get prepared for work which the *i*-th candidate spends each morning. This time doesn't depend on day. The parameter *r*_{i} is the total working time needed for the *i*-th candidate to accomplish the whole test exercise.

Thus the time spent in the office in the *j*-th day consists of *d*_{i} units of time to get prepared and some units of time to proceed with the exercise. A candidate can skip entire working day and do not come to the office. Obviously in this case he doesn't spend *d*_{i} units of time to prepare.

To complete the exercise a candidate should spend exactly *r*_{i} units of time working on the exercise (time to prepare is not counted here).

Find out for each candidate what is the earliest possible day when he can fully accomplish the test exercise. It is allowed to skip working days, but if candidate works during a day then he must spend *d*_{i} units of time to prepare for work before he starts progressing on the exercise.

Input

The first line contains two integer numbers *n*, *m* (1 ≤ *n*, *m* ≤ 2·10^{5}) — the number of candidates and the maximum number of working days to do the test exercise.

The second line contains *m* integer numbers *t*_{1}, *t*_{2}, ..., *t*_{m} (1 ≤ *t*_{j} ≤ 10^{6}) — the durations of working days in time units.

The following *n* lines contain two integers each: *d*_{i}, *r*_{i} (0 ≤ *d*_{i} ≤ 10^{6}, 1 ≤ *r*_{i} ≤ 10^{6}) — how much time in the beginning of a day is required for *i*-th candidate before he starts his work on the test exercise and how much time it is needed for him to accomplish this task.

Output

Output a sequence of *n* integer numbers *b*_{1}, *b*_{2}, ..., *b*_{n}, where *b*_{i} is the earliest day when the *i*-th candidate can finish the test exercise.

In case the *i*-th candidate cannot finish the test exercise in *m* days output *b*_{i} = 0.

Days in this problem are numbered from 1 to *m* in the order they are given in the input.

Examples

Input

3 3

4 2 5

1 3

2 5

3 4

Output

1 3 0

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/24/2017 07:58:21 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|