Seating of Students
Contest: Технокубок 2018 - Отборочный Раунд 4
Difficulty rating: 2200
Tags: constructive algorithms

Students went into a class to write a test and sat in some way. The teacher thought: "Probably they sat in this order to copy works of each other. I need to rearrange them in such a way that students that were neighbors are not neighbors in a new seating."

The class can be represented as a matrix with n rows and m columns with a student in each cell. Two students are neighbors if cells in which they sit have a common side.

Let's enumerate students from 1 to n·m in order of rows. So a student who initially sits in the cell in row i and column j has a number (i - 1)·m + j. You have to find a matrix with n rows and m columns in which all numbers from 1 to n·m appear exactly once and adjacent numbers in the original matrix are not adjacent in it, or determine that there is no such matrix.

Input format:
The only line contains two integers n and m (1 ≤ n, m ≤ 105; n·m ≤ 105) — the number of rows and the number of columns in the required matrix.

Output format:
If there is no such matrix, output "NO" (without quotes).

Otherwise in the first line output "YES" (without quotes), and in the next n lines output m integers which form the required matrix.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case the matrix initially looks like this:

It's easy to see that there are no two students that are adjacent in both matrices.

In the second test case there are only two possible seatings and in both of them students with numbers 1 and 2 are neighbors.

Example input:
2 4

Example output:
YES
5 4 7 2
3 6 1 8

Example input:
2 1

Example output:
NO

Editorial:
The problem has many solutions, including random ones. Consider one of deterministic solutions. Without loss of generality, assume that n ≤ m.
There are a couple of corner cases:
1. n = 1, m = 1. In this case, good seating exists.
2. n = 1, m = 2. In this case, seating does not exist (obviously).
3. n = 1, m = 3. In any seating, one of neighbours of student 2 will be one of his former neighbours, so correct seating does not exist.
4. n = 2, m = 2. Only student 4 can be a neighbour of student 1, but there should be 2 neighbours for student 1; then, correct seating does not exist.
5. n = 2, m = 3. Both students 5 and 2 have 3 neighbours in the initial seating; then, in new seating, these students should be in non-neighbouring corner cells. Moreover, these corner cells can not be in one row because in this case it's impossible to find a student for cell between 2 and 5. So, without loss of generality, let 5 be in lower left corner, and 2 — in upper right corner. Then, only students 1 and 3 can seat on lower middle cell; but if sduent 1 seats in the cell, then student 4 is impossible to seat at any of the remaining cells, so do student 6 in case of student 3 seating at the cell. So, correct seating does not exist in this case too.
6. n = 1, m = 4. In this case, one of correct seatings is 2 4 1 3.
7. n = 1;5 ≤ m. In this case, let students with odd numbers in increasing order will be in first half of the row, and others in increasing order - in second half. For example, for m = 7 the seating will be 1 3 5 7 2 4 6.
8. n = m = 3. One of possible correct seatings is:6 1 87 5 32 9 4;
9. If 2 ≤ n;4 ≤ m, then shift each even row cyclically on two symbols in the right, and then shift each even column cyclically on one symbol upwards. If students are vertical neighbours in the initial seating, then in new seating, they will be in different columns on the distance 2 (possibly through the edge of the table); but if students are horizontal neighbours in the initial seating, then in new seating they will be in neighbouring rows and neighbouring columns (possibly thorugh the edges again). So, for case 2 ≤ n, 4 ≤ m, we build a correct seating.