A. Generator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Implement a uniform generator of pseudo-random pairs of integers ($$$a$$$, $$$b$$$) such that $$$1 \le a \le b \le k$$$. Explanation: each valid pair should be generated with equal probability upon each call to the generator.

Input

The first line of the input contains an integer $$$k$$$ ($$$2 \le k \le 10^9$$$).

The second line contains an integer $$$n$$$ — the number of pairs to generate ($$$1 \le n \le 10000$$$).

Output

Using the created generator, generate and output $$$n$$$ pairs. Output each pair on a separate line, separate elements of pairs with a space.

Example
Input
5
3
Output
1 4
3 5
2 2
Note

When checking solutions, it will be checked whether the resulting sample follows a uniform distribution law over the interval of acceptable values. No other quality checks of your generator will be performed.