CF317B.Ants

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.

人们发现，若将一些蚂蚁放置在石墨烯整数格点的交点上，则它们会按如下方式行动：每一分钟，在每个至少有四只蚂蚁的交点 $(x, y)$ 处，会形成一组四只蚂蚁，这四只蚂蚁将分别散向相邻的四个交点 $(x+1, y)$、$(x-1, y)$、$(x, y+1)$、$(x, y-1)$——每个方向各一只。除此之外，不会发生其他蚂蚁移动。蚂蚁之间互不干扰。

科学家们将一个由 $n$ 只蚂蚁组成的蚁群放入交点 $(0, 0)$，现在他们希望知道：当蚂蚁运动停止后，某些指定交点上各有多少只蚂蚁。

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 ( - 109 ≤ x__i, y__i ≤ 109). 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).

第一行输入包含两个整数 $n$（$0 \leq n \leq 30000$）和 $t$（$1 \leq t \leq 50000$），其中 $n$ 表示蚁群中蚂蚁的数量，$t$ 表示查询次数。接下来的 $t$ 行每行包含一个查询路口的坐标：整数 $x_i$、$y_i$（$-10^9 \leq x_i, y_i \leq 10^9$）。查询点可能重合。

保证存在某个时刻，使得不再可能发生任何移动（即该过程最终会终止）。

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

输出 t 个整数，每行一个——即蚂蚁停止移动时，对应路口处的蚂蚁数量。

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.

在第一个样例中，蚁群仅由一只蚂蚁组成，因此不会发生任何事情。

在第二个样例中，蚁群由 6 只蚂蚁组成。在第一分钟，有 4 只蚂蚁从 $(0, 0)$ 散开至相邻的路口。此后该过程停止。