CF1634C.OKEA

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

People worry that computers will get too smart and take over the world, but the real problem is that they're too stupid and they've already taken over the world.

— Pedro Domingos

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⋅kn \cdot k items. The first item costs 11 dollar, the second item costs 22 dollars, and so on: ii-th item costs ii dollars. The items are situated on shelves. The items form a rectangular grid: there are nn shelves in total, and each shelf contains exactly kk items. We will denote by ai,ja_{i,j} the price of jj-th item (counting from the left) on the ii-th shelf, 1≤i≤n,1≤j≤k1 \le i \le n, 1 \le j \le k.

Occasionally robots get curious and ponder on the following question: what is the mean price (arithmetic average) of items ai,l,ai,l+1,…,ai,ra_{i,l}, a_{i,l+1}, \ldots, a_{i,r} for some shelf ii and indices l≤rl \le 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 aa that:

  • Every number from 11 to n⋅kn \cdot k (inclusively) occurs exactly once.
  • For each i,l,ri, l, r, the mean price of items from ll to rr on ii-th shelf is an integer.

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

人们担心计算机会变得过于聪明,从而接管世界,但真正的问题是它们太愚蠢了,而且早已接管了世界。

——佩德罗·多明戈斯

你受雇于一家知名百货商店,该商店采用前沿技术,并实行机械化作业——即使用机器人!

你所在的部门销售 n⋅kn \cdot k 件商品。第一件商品售价为 11 美元,第二件售价为 22 美元,依此类推:第 ii 件商品售价为 ii 美元。这些商品摆放在货架上,构成一个矩形网格:共有 nn 层货架,每层货架恰好摆放 kk 件商品。我们用 ai,ja_{i,j} 表示第 ii 层货架(从上往下数)从左往右数第 jj 件商品的价格,其中 1≤i≤n, 1≤j≤k1 \le i \le n,\, 1 \le j \le k。

有时机器人会感到好奇,并思考如下问题:对于某一层货架 ii 及其上一段连续区间 [l,r][l, r](即商品 ai,l,ai,l+1,…,ai,ra_{i,l}, a_{i,l+1}, \ldots, a_{i,r}),这些商品价格的平均值(算术平均数)是多少?不幸的是,老式机器人只能处理整数。若该平均值不是整数,机器人便会宕机。

你关心机器人的福祉。你希望以某种方式摆放商品,使得机器人在理论上绝不会宕机。形式化地说,你需要构造一个二维数组 aa,满足:

  • 11 到 n⋅kn \cdot k(含端点)之间的每个整数恰好出现一次;
  • 对任意 i,l,ri, l, r,第 ii 层货架上从第 ll 个到第 rr 个商品的价格平均值均为整数。

请判断是否存在满足上述条件的摆放方式;若存在,请给出任意一种具体方案。

输入格式

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

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

It is guaranteed that the sum nn over all test cases does not exceed 500500 and the sum kk over all test cases does not exceed 500500.

第一行包含一个整数 tt(1≤t≤5001 \le t \le 500)—— 表示测试用例的数量。

每个测试用例仅有一行,包含两个整数 nn 和 kk(1≤n,k≤5001 \le n, k \le 500)—— 分别表示书架的数量以及每个书架的长度。

保证所有测试用例的 nn 之和不超过 500500,且所有测试用例的 kk 之和不超过 500500。

输出格式

Print the answer for each test case.

If such an arrangement exists, print "YES" on a single line. After that, print any example on nn lines of kk numbers each, one line per shelf. Each number from 11 to n⋅kn \cdot k must occur exactly once in the output.

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

对每个测试用例,输出答案。

如果这样的排列存在,则在单独一行上输出 "YES"。之后,在接下来的 nn 行中,每行输出 kk 个数字(即每行对应一个书架)。输出中必须恰好包含从 11 到 n⋅kn \cdot k 的每个数字各一次。

如果不存在满足条件的排列,则在单独一行上输出单词 "NO"。

输入输出样例

  • 输入#1

    4
    1 1
    2 2
    3 3
    3 1

    输出#1

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

输入解题思路,AI测评打分。不知道怎么写?

首页