У Алисы недавно появилась новая кукла. Она даже может ходить!
Алиса построила лабиринт для куклы и хочет протестировать его. Лабиринт имеет вид таблицы с \(n\) строками и \(m\) столбцами. Также есть \(k\) препятствий, \(i\)-е из них находится в клетке \((x_i, y_i)\), это клетка на пересечении строки с номером \(x_i\) и столбца с номером \(y_i\).
Однако кукла очень неуклюжая. Она может только идти прямо и поворачиваться направо, но не больше одного раза в одной клетке (включая стартовую клетку). Она не может переходить в клетку с препятствием, а также покидать пределы лабиринта.
Более формально, всего существует \(4\) направления, в которых может смотреть кукла:
- Кукла смотрит в направлении вдоль строки от первой клетки к последней. Перемещаясь смотря в этом направлении, кукла переходит из клетки \((x, y)\) в клетку \((x, y + 1)\);
- Кукла смотрит в направлении вдоль столбца от первой клетки к последней. Перемещаясь смотря в этом направлении, кукла переходит из клетки \((x, y)\) в клетку \((x + 1, y)\);
- Кукла смотрит в направлении вдоль строки от последней клетки к первой. Перемещаясь смотря в этом направлении, кукла переходит из клетки \((x, y)\) в клетку \((x, y - 1)\);
- Кукла смотрит в направлении вдоль столбца от последней клетки к первой. Перемещаясь смотря в этом направлении, кукла переходит из клетки\((x, y)\) в клетку \((x - 1, y)\).
.
Находясь в некоторой клетке, кукла может перейти в клетку в направлении, в котором она смотрит, либо повернуться один раз направо. Поворачиваясь один раз направо, кукла меняет направление, в котором она смотрит следующим образом: \(1 \to 2\), \(2 \to 3\), \(3 \to 4\), \(4 \to 1\). В одной клетке, кукла может совершить не более одного поворота направо.
Сейчас Алиса управляет перемещениями куклы. Изначально она поставила куклу в клетку \((1, 1)\) (верхняя левая клетка лабиринта). Изначально кукла смотрит в направлении \(1\), то есть в направлении вдоль строки от первой клетки к последней. Она хочет обойти куклой все клетки лабиринта, не содержащие препятствий ровно по одному разу и закончить в любой клетке. Существует ли способ так сделать?
Выходные данные
Выведите 'Yes' (без кавычек) если кукла может обойти все клетки, не содержащие препятствий по описанным выше правилам ровно по одному разу.
Если так обойти лабиринт невозможно, выведите 'No' (без кавычек).
Примечание
Картинка с лабиринтом из первого примера:
В первом примере, кукла может идти по следующему пути:
- Кукла в клетке \((1, 1)\), смотрит в направлении \(1\). Пройти прямо;
- Кукла в клетке \((1, 2)\), смотрит в направлении \(1\). Пройти прямо;
- Кукла в клетке \((1, 3)\), смотрит в направлении \(1\). Повернуть направо;
- Кукла в клетке \((1, 3)\), смотрит в направлении \(2\). Пройти прямо;
- Кукла в клетке \((2, 3)\), смотрит в направлении \(2\). Пройти прямо;
- Кукла в клетке \((3, 3)\), смотрит в направлении \(2\). Повернуть направо;
- Кукла в клетке \((3, 3)\), смотрит в направлении \(3\). Пройти прямо;
- Кукла в клетке \((3, 2)\), смотрит в направлении \(3\). Пройти прямо;
- Кукла в клетке \((3, 1)\), смотрит в направлении \(3\). Цель достигнута, все клетки лабиринта, не содержащие препятствия посещены ровно один раз.