OKEA codeforces solution – JAVA, Python, C++

You work for a well-known department store that uses leading technologies and employs mechanistic work — that is, robots!

The department you work in sells 𝑛𝑘n⋅k items. The first item costs 11 dollar, the second item costs 22 dollars, and so on: 𝑖i-th item costs 𝑖i dollars. The items are situated on shelves. The items form a rectangular grid: there are 𝑛n shelves in total, and each shelf contains exactly 𝑘k items. We will denote by 𝑎𝑖,𝑗ai,j the price of 𝑗j-th item (counting from the left) on the 𝑖i-th shelf, 1𝑖𝑛,1𝑗𝑘1≤i≤n,1≤j≤k.

Occasionally robots get curious and ponder on the following question: what is the mean price (arithmetic average) of items 𝑎𝑖,𝑙,𝑎𝑖,𝑙+1,,𝑎𝑖,𝑟ai,l,ai,l+1,…,ai,r for some shelf 𝑖i and indices 𝑙𝑟l≤r? Unfortunately, the old robots can only work with whole numbers. If the mean price turns out not to be an integer, they break down.

You care about robots’ welfare. You want to arrange the items in such a way that the robots cannot theoretically break. Formally, you want to choose such a two-dimensional array 𝑎a that:

  • Every number from 11 to 𝑛𝑘n⋅k (inclusively) occurs exactly once.
  • For each 𝑖,𝑙,𝑟i,l,r, the mean price of items from 𝑙l to 𝑟r on 𝑖i-th shelf is an integer.

Find out if such an arrangement is possible, and if it is, give any example of such arrangement.

Input

The first line contains a single integer 𝑡t (1𝑡5001≤t≤500) — the number of test cases.

The first and only line of each test case contains two integers 𝑛n and 𝑘k (1𝑛,𝑘5001≤n,k≤500) — the number of shelves and length of each shelf, respectively.

It is guaranteed that the sum 𝑛n over all test cases does not exceed 500500 and the sum 𝑘k over all test cases does not exceed 500500.

Output

Print the answer for each test case.

If such an arrangement exists, print “YES” on a single line. After that, print any example on 𝑛n lines of 𝑘k numbers each, one line per shelf. Each number from 11 to 𝑛𝑘n⋅k must occur exactly once in the output.

If no good arrangement exists, print a single word “NO” on its own line.

Example
input

Copy
4
1 1
2 2
3 3
3 1
output

Copy
YES
1 
YES
1 3 
2 4 
NO
YES
1 
2 
3 

 

Leave a Comment