#GYM104787A. Make SYSU Great Again I
Make SYSU Great Again I
Description
As you know, you guys are participating in CCPC (Chinese Constructive Problem Contest), and no doubt that the proposition school SYSU, as the kingdom of constructive problems, is going to challenge you to solve some related problems.
Given an $n \times n$ grid, you are asked to fill each number in $[1,k]$ into the grid, and it needs to fulfill the following requirements.
- Each number from $1$ to $k$ occurs exactly once.
- Each cell should be filled with at most one number.
- Each row and column has at least two numbers.
- For each integer $i\in [1,n]$, the greatest common divisor of all numbers in row $i$ is equal to the greatest common divisor of all numbers in column $i$.
It's guaranteed that there must be a valid solution under the restriction of the problem.
The only line contains two integers $n$ and $k\ (\ 2\leq n\leq 2\times 10^5,\ 2\times n \leq k\leq min(n^2,10^6)\ )$ — the size of the grid and the numbers you need to fill in.
You should output $k$ lines, with line $i$ consisting of two integers $x_i$, $y_i$ representing the rows and columns of the position filled by the number $i$, respectively.
If there are multiple solutions, you can output any one.
Input
The only line contains two integers $n$ and $k\ (\ 2\leq n\leq 2\times 10^5,\ 2\times n \leq k\leq min(n^2,10^6)\ )$ — the size of the grid and the numbers you need to fill in.
Output
You should output $k$ lines, with line $i$ consisting of two integers $x_i$, $y_i$ representing the rows and columns of the position filled by the number $i$, respectively.
If there are multiple solutions, you can output any one.
3 6
1 1
2 2
1 3
2 3
3 1
3 2