← 返回题目列表

Codeforces · 317/B

B. 蚂蚁

中文机器翻译题面 查看原题

值得注意的是,如果将一些蚂蚁放入石墨烯整数晶格的连接处,那么它们将按照以下方式行动:每分钟在每个包含至少四只蚂蚁的连接处(x,y),将形成一组四只蚂蚁,这四只蚂蚁将分散到相邻的连接处(x + 1,y),(x - 1,y),(x,y + 1),(x,y) - 1) — 每个方向一只蚂蚁。不会发生其他蚂蚁运动。蚂蚁从不互相干扰。

科学家将一群 n 只蚂蚁放入交叉点 (0, 0),现在他们想知道当蚂蚁停止移动时,在某些给定的交叉点上会有多少只蚂蚁。

输入

第一输入行包含整数 n (0 ≤ n ≤ 30000) 和 t (1 ≤ t ≤ 50000),其中 n 是蚁群中蚂蚁的数量,t 是查询的数量。接下来的 t 行中的每一行都包含查询连接点的坐标:整数 xi, yi (- 109 ≤ xi, yi ≤ 109)。查询可能会重合。

保证在某个时刻不可能发生任何可能的运动(换句话说,该过程最终会结束)。

输出

打印t个整数,每行一个——当蚂蚁停止运动时,相应路口的蚂蚁数量。

示例

输入 #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

注意

在第一个样本中,蚁群由一只蚂蚁组成,因此什么也没有发生。

在第二个样本中,蚁群由 6 只蚂蚁组成。第一分钟,4 只蚂蚁从 (0, 0) 分散到邻近的路口。之后该过程停止。