Прыжки с поворотом
Прыжки с поворотом
Ване снится сон, что он стоит на клетчатом поле размера n * m, и ему хочется побывать во всех клетках этого поля ровно по одному разу.
Ваня может исходно встать в центр любой клетки и затем может перепрыгивать из клетки, где он находится, на другую клетку. После прыжка Ваня оказывается в центре соответствующей клетки.
Ваня может допрыгнуть от любой клетки до любой другой, но не все так просто. Каждый раз после прыжка он должен поворачиваться строго налево. А именно, для любых трех клеток, которые Ваня посетил подряд, должно выполняться следующее условие: если смотреть из центра первой клетки в направлении центра второй клетки, то центр третьей клетки должен лежать в левой полуплоскости, не включая саму прямую между центрами первой и второй клетки. В частности, центры трех подряд идущих клеток не должны лежать на одной прямой.
Столбцы поля пронумерованы слева направо от 1 до n, а строки — снизу вверх от 1 до m. Помогите Ване, найдите способ посетить все клетки, либо определите, что это невозможно.
Входные данные
В единственной строке находятся два целых числа n и m—количество столбцов и строк (1 ≤ n,m ≤ 100).
Выходные данные
В первой строке выведите «Yes», если посетить все клетки описанным способом возможно, иначе выведите «No».
Если решение существует, выведите еще n * m строк, в i-й из которых выведите два целых числа xi
и yi
— номер столбца и номер строки, на пересечении которых находится клетка, в которую Ваня должен прыгнуть i-й по счету (1 ≤ xi ≤ n, 1 ≤ yi ≤ m)
.
Пояснение для первого теста
Пояснение для второго теста
2 2
Yes 1 1 2 2 1 2 2 1
4 2
Yes 4 1 2 2 1 1 4 2 3 2 2 1 3 1 1 2