Монокарп пришел в ретро игровой клуб с аркадными автоматами. Там его заинтересовал автомат «Поймай монетку».
Игра довольно простая. Экран представляет собой координатную сетку такую, что:
- ось OX направлена слева направо;
- ось OY направлена снизу вверх;
- центр экрана имеет координаты \((0, 0)\).
В начале игры персонаж находится в центре, а на экране появляются \(n\) монет — \(i\)-я монета в координате \((x_i, y_i)\). Координаты всех монет различны и не равны \((0, 0)\).
За одну секунду Монокарп может подвинуть персонажа в одном из восьми направлений. Если персонаж находится в координате \((x, y)\), то он может оказаться в любой из координат \((x, y + 1)\), \((x + 1, y + 1)\), \((x + 1, y)\), \((x + 1, y - 1)\), \((x, y - 1)\), \((x - 1, y - 1)\), \((x - 1, y)\), \((x - 1, y + 1)\).
Если персонаж оказывается в координате с монеткой, то Монокарп собирает эту монетку.
После того как Монокарп сделал ход, все монетки падают на \(1\) вниз, то есть, перемещаются из \((x, y)\) в \((x, y - 1)\). Можете считать, что игровое поле бесконечное во все стороны.
Монокарп хочет собрать хотя бы одну монетку, но никак не может определиться, за какой монеткой бежать. Помогите ему определить для каждой монеты, может ли он ее собрать.
Примечание
Обратите внимание на вторую монетку в примере. Монокарп может сначала сходить из \((0, 0)\) в \((-1, -1)\). Затем монета падает на \(1\) вниз и оказывается в \((-2, -2)\). Наконец Монокарп ходит в \((-2, -2)\) и собирает монету.