Задача G. Шахтеры Online

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб

Условие

Денис и Женя захотели вместе поиграть в новую игру — «Шахтёры Online». Пока Женя пошел обустраивать базу и строить дом, Денис отправился в шахту за самым ценным ресурсом в игре — за алмазами. Зона, которую будет копать Денис, представляет собой поле n × n × n клеток. Алмазы в Шахтерах Онлайн находятся на n-м уровне по высоте. Денис уже хорошо изучил игру и точно знает, что алмазы будут находится на координате (x,y).

Рост персонажа в игре — одна клетка. Копать Денис может в пределах слоях на соседние клетки — вперед, назад, влево и вправо (Денис пользуется эффективной техникой копания, поэтому он сразу входит в скопанную клетку). Также Денис может копать под себя и провалиться на уровень ниже. Возвращаться же на уровни выше он не хочет, потому что он хочет похвастаться добытыми алмазами как можно быстрее. Но не стоит забывать, о том, что в мире «Шахтёров Online» есть лава, и Денис не очень хочет с ней сталкиваться или провалиться в неё. Также Денису следует быть осторожным, потому что лава имеет физику, может стечь на него сверху, ещё она разливается на одну клетку во все стороны, если клетка пустая (считается, что если Денис ломает клетку рядом с источником лавы, то лава мгновенно стекает на образовавшееся пространство, из-за чего Денису придется с ней контактировать).

Изначально Денис находится на свежем воздухе (на нулевом слое по высоте), поэтому он может выбрать клетку, с которой он начнет копать.

Помогите Денису определить, сможет ли он похвастаться перед Женей алмазами!

Формат входных данных

В первой строке входных данных вводятся числа n и q — размер поля и количество блоков с лавой (2 ≤ n ≤ 100, 0 ≤ q ≤ n3 − 1). В следующих q строках вводятся числа hi, xi и yi, которые показывают, что на hi-м слое сверху в клетке с координатами (xi, yi) находится блок лавы. В последней строке вводятся числа x и y — координаты алмазов.

Формат выходных данных

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

Примеры тестов

Стандартный вход Стандартный выход
1
3 4
2 1 1
2 1 3
2 3 1
2 3 3
2 2
YES
2
2 4
1 1 1
1 1 2
1 2 1
1 2 2
1 1
NO

0.086s 0.024s 15