Madeline has arrived at the Sky Resort, where she encounters paths covered in soot. These paths can only be traversed once; crossing them multiple times will cause the soot to corrupt her. The hotel owner explains the rules for leaving:
The entire resort has $n$ rooms. Every room except for the starting room (room $1$) contains a strawberry. There is exactly one soot-covered path connecting every pair of rooms. Every time you take $k$ steps, you pick up the strawberry in the current room. If the strawberry in the current room has already been picked up, the owner will eat you.
You need to collect all the strawberries to successfully leave.
Simplified Problem Statement
There is a complete graph with $n$ vertices. You need to construct a path starting from $1$ with a length of $k(n-1)$, such that the vertices reached every $k$ steps are distinct and are not the starting vertex. Each edge can be traversed at most once (once traversed in one direction, it cannot be traversed in the opposite direction).
Input
A single line containing two integers $n$ and $k$, as described above.
Output
A single line containing $k(n-1)$ integers, representing the destination of each step. Any valid solution is acceptable.
Examples
Input 1
3 1
Output 1
2 3
Input 2
5 2
Output 2
2 5 4 2 3 4 1 3
Note
Madeline leaves the resort after picking up strawberries in rooms $5, 2, 4, 3$ in sequence.
Note that the example does not satisfy the constraints; it is only provided to help understand the problem.
Constraints
For all data, $n \times k \le 1 \times 10^6$, $n \ge \max(2k+15, 30)$, and $k \ge 1$.
- Subtask 1 (5 pts): $k \le 2$
- Subtask 2 (20 pts): $n \ge 4k^2+229$
- Subtask 3 (20 pts): $n \ge 5k+15$
- Subtask 4 (20 pts): $k$ is $229$, $233$, $114$, or $514$.
- Subtask 5 (35 pts): No special constraints.