Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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

B. Ants

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIt has been noted that if some ants are put in the junctions of the graphene integer lattice then they will act in the following fashion: every minute at each junction (*x*, *y*) containing at least four ants a group of four ants will be formed, and these four ants will scatter to the neighbouring junctions (*x* + 1, *y*), (*x* - 1, *y*), (*x*, *y* + 1), (*x*, *y* - 1) — one ant in each direction. No other ant movements will happen. Ants never interfere with each other.

Scientists have put a colony of *n* ants into the junction (0, 0) and now they wish to know how many ants will there be at some given junctions, when the movement of the ants stops.

Input

First input line contains integers *n* (0 ≤ *n* ≤ 30000) and *t* (1 ≤ *t* ≤ 50000), where *n* is the number of ants in the colony and *t* is the number of queries. Each of the next *t* lines contains coordinates of a query junction: integers *x*_{i}, *y*_{i} ( - 10^{9} ≤ *x*_{i}, *y*_{i} ≤ 10^{9}). Queries may coincide.

It is guaranteed that there will be a certain moment of time when no possible movements can happen (in other words, the process will eventually end).

Output

Print *t* integers, one per line — the number of ants at the corresponding junctions when the movement of the ants stops.

Examples

Input

1 3

0 1

0 0

0 -1

Output

0

1

0

Input

6 5

0 -2

0 -1

0 0

0 1

0 2

Output

0

1

2

1

0

Note

In the first sample the colony consists of the one ant, so nothing happens at all.

In the second sample the colony consists of 6 ants. At the first minute 4 ants scatter from (0, 0) to the neighbouring junctions. After that the process stops.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/29/2020 19:02:14 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|