Ants

题意翻译

平面直角坐标系中，初始时在(0,0)处有n只蚂蚁。 每分钟，如果存在一个位置(x,y)的蚂蚁数量至少为4， 那么这4只蚂蚁将分别向四个方向移动：(x+1,y)(x-1,y)(x,y-1)(x,y+1)。 如果存在多个位置蚂蚁数量都>=4,这些位置上的蚂蚁将同时按上述方式向四个方向移动，且互不干扰。 求当所有蚂蚁停止移动时，某个位置上的蚂蚁数量。

题目描述

It 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.

输入输出格式

输入格式

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).

输出格式

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

输入输出样例

输入样例 #1

1 3
0 1
0 0
0 -1

输出样例 #1

0
1
0

输入样例 #2

6 5
0 -2
0 -1
0 0
0 1
0 2

输出样例 #2

0
1
2
1
0

说明

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.