Description

给定一个 $n\times n\left(2\leqslant n\leqslant 2\times 10^5\right)$ 的网格，你需要将 $\left[1,k\right]\left(2\times n\leqslant k\leqslant \min(n^2,10^{6})\right)$ 内的每个整数填入网格中，并且满足以下要求：

1. 数字 $1$ 到 $k$ 恰好出现一次；
2. 每个单元格最多填入一个数字；
3. 每行和每列至少有两个数字；
4. 对于每个整数 $i\in \left[1,n\right]$，第 $i$ 行的所有数字的最大公约数应等于第 $i$ 列所有数字的最大公约数。

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

Format

Input

一行两个正整数，$n,k$，表示矩阵的大小和需要填入的数字数量。

Output

输出 $k$ 行，第 $i$ 行包含两个整数 $x_i,y_i$，表示数字 $i$ 填入位置所对应的行号和列号。

Samples

3 6

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

Limitation

1s, 1024KiB for each test case.