值得注意的是,如果将一些蚂蚁放入石墨烯整数晶格的连接处,那么它们将按照以下方式行动:每分钟在每个包含至少四只蚂蚁的连接处(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) 分散到邻近的路口。之后该过程停止。