B. Муравьи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Во время исследования поведения муравьев в графеновых трубках на целочисленной решетке было сделано следующее важное наблюдение об их поведении: каждую минуту в каждом узле (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 3
0 1
0 0
0 -1
Выходные данные
0
1
0
Входные данные
6 5
0 -2
0 -1
0 0
0 1
0 2
Выходные данные
0
1
2
1
0
Примечание

В первом примере колония состоит всего из одного муравья, и никаких движений не происходит.

Во втором примере колония состоит из 6 муравьев. На первой минуте 4 муравья из (0, 0) разбегаются в соседние узлы. После этого процесс останавливается.