Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Во время исследования поведения муравьев в графеновых трубках на целочисленной решетке было сделано следующее важное наблюдение об их поведении: каждую минуту в каждом узле (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) разбегаются в соседние узлы. После этого процесс останавливается.