Каждый год Дед Мороз дарит подарки всем детям. Однако в каждой стране есть свои традиции, и этот процесс происходит по разному. Например в Берляндии нужно решить новогоднюю головоломку.
Поликарпу досталась следующая задача: дана клетчатая полоска размером \(2 \times n\), некоторые клетки на ней заблокированы. Нужно проверить, можно ли замостить все незаблокированные клетки с помощью дощечек \(2 \times 1\) и \(1 \times 2\).
Например, если \(n = 5\) и полоска имеет следующий вид (черные клетки заблокированы):
То ее можно замостить, например, используя две вертикальных и две горизонтальных, как на картинке ниже (разные дощечки обозначаются разным цветом).
А если \(n = 3\) и полоска имеет следующий вид:
То замостить свободные клетки невозможно.
Поликарп легко справился с этой задачей и получил свой новогодний подарок. А сможете ли вы решить ее?
Выходные данные
Для каждого набора входных данных в отдельной строке выведите:
- «YES», если можно ли замостить все незаблокированные клетки с помощью дощечек \(2 \times 1\) и \(1 \times 2\);
- «NO» в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
Примечание
Первые два набора входных данных разобраны в условии.
В третьем наборе входных данных полоска выглядит следующим образом
Несложно убедиться, что свободные клетки на ней нельзя замостить
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 2
2 2
1 4
3 2
2 1
2 3
6 4
2 1
2 3
2 4
2 6
|
YES
NO
NO
|