아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Jump and turn

시간 제한1초메모리 제한512 MB

요약
n x m 격자의 모든 칸을 정확히 한 번씩 방문하되, 연속한 세 방문 칸의 중심이 엄격히 왼쪽으로 꺾이도록 순서를 정한다.
난이도

보통10점 중 7점

유형
구현, 그리디, 기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

Vanya is now sleeping and in the dream he's standing on grid of size n×mn \times m. He wants to visit every cell of grid exactly once.

Vanya can initialy stand in the center of any cell and then he can jump from the cell he's standing on now to any other cell. Every time Vanya jumps exactly to the center of cell.

Vanya can jump from any cell to any other cell but there's a problem. Every time after jump he must turn strictly left. Specifically any three cells Vanya visit successively must satisfy following: if stand in the center of first cell and look at center of second cell then center of third cell must be in the left half-plane excluding line between centers of first and second cells. Particularly centers of three successively visited cells must not lie on one straight line.

Columns of grid are numbered from left to right from 11 to nn. Rows of grid are numbered from bottom to top from 11 to mm.

Help Vanya to find a way to visit every cell exactly once and satisfy the condition or report if it's impossible.

입력

Single line contains two integers nn and mm --- amount of columns and rows (1≤n,m≤1001 \le n, m \le 100).

출력

In first line output <<Yes>> if it is possible to visit every cell as described, output <<No>> otherwise.

If solution exists output n⋅mn \cdot m more lines, ii-th of them contains two integers x_ix\_i and y_iy\_i --- numbers of column and row which contains a cell Vanya should visit on ii-th step (1≤x_i≤n1 \le x\_i \le n, 1≤y_i≤m1 \le y\_i \le m).

힌트

Explanation for the first test

Explanation for the second test

예제2

  1. 예제 1

    입력
    2 2
    
    예상 출력
    Yes
    1 1
    2 2
    1 2
    2 1
    
  2. 예제 2

    입력
    4 2
    
    예상 출력
    Yes
    4 1
    2 2
    1 1
    4 2
    3 2
    2 1
    3 1
    1 2