1224 : 贵校是构造王国吗 I

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
256 兆MB
提交次数Submitted
220 次Times
通过次数Solved
88 次Times

题目描述Description

众所周知,你们正在参加中国构造题竞赛(Chinese Constructive Problem Contest, CCPC),毫无疑问,命题学校中山大学身为构造王国非常希望你们去挑战一些相关的问题。

给定一个 \(n \times n\) 的网格,你需要将 \([1,k]\) 内的填入网格中,并且满足以下要求。

  • 数字 \(1\) 到 \(k\) 恰好出现一次。

  • 每个单元格最多填入一个数字。

  • 每行和每列应至少有两个数字。

  • 对于每个整数 \(i\in [1,n]\),第 \(i\) 行所有数字的最大公约数应等于第 \(i\) 列所有数字的最大公约数。

保证在输入的限制下一定存在一个合法的方案。

输入格式Input

输入只有一行,包含两个整数 \(n\) 和 \(k\ (\ 2\leq n\leq 2\times 10^5,\ 2\times n \leq k\leq min(n^2,10^6)\ )\) — 表示矩阵的大小和需要填入的数字数量。

输出格式Output

你应该输出 \(k\) 行,第 \(i\) 行由两个整数 \(x_i\) 和 \(y_i\) 组成,表示数字 \(i\) 填入位置所对应的行号和列号。

如果有多种方案,输出任意一个即可。

样例Sample

出题Author

SYSU