1224 : 贵校是构造王国吗 I

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

3 6

1 1
2 2
1 3
2 3
3 1
3 2

Hint

Source