Весь мир охватила роботомания и, чтобы не отставать от прогресса, великий берляндский программист Дравдэ решил создать собственного робота. Дравдэ долго и упорно трудился над роботом. Он научил его ходить кратчайшим путем из одной точки в другую, научил записывать все свои передвижения, но, как и во многих программах Дравдэ, нашелся баг — робот не всегда ходил кратчайшими путями. Благо, что собственные передвижения робот записывал правильно. Теперь Дравдэ хочет узнать, когда его робот неправильно работает. Эх, если бы Дравдэ помнил карту местности, на которой происходило тестирование робота, он бы легко сказал правильно прошел робот или нет. Но карта местности безвозвратно потерялась, и поэтому он поручает вам проверить: существует ли хотя бы одна такая карта, на которой путь записанный роботом является кратчайшим.

Карта представляет собой бесконечное клетчатое поле, где каждая клетка либо пустая, либо содержит препятствие. Также известно, что робот никогда не пытается врезаться в препятствие. По записи робота о его передвижении определите, существует ли хотя бы одна такая карта, что на ней можно выбрать стартовую клетку для робота (стартовая клетка должна быть пустой), при движении из которой запись корректна (робот ни во что не врезается, двигаясь только по пустым клеткам), и путь из стартовой точки в конечную является кратчайшим.

За один ход робот может передвинуться на любую соседнюю по стороне клетку, если она не является препятствием.