Description

As we all know, Xiao Cong is good at calculations, especially at computing binomial coefficients. So Xiao Cong gives you two numbers $x$ and $k$, and wants you to express $x$ as the sum of exactly $k$ distinct binomial coefficients. By distinct, we mean that for two binomial coefficients $C(n_1, m_1)$ and $C(n_2, m_2)$, if $n_1 \neq n_2$ or $m_1 \neq m_2$, then these two binomial coefficients are considered different. To keep the computation from being too complex, you must ensure that every binomial coefficient $C(n, m)$ you provide satisfies $0 \leq m \leq n \leq x$. It is guaranteed that there is a solution.

Input Format

Read from standard input.

The first line contains two integers $x, k$.

Output Format

Output to standard output.

Output $k$ lines. Each line contains two integers $n, m$ representing a binomial coefficient $C(n, m)$. If multiple answers are possible, output any one of them.

6 2

3 1
3 2

Hint

For $20\%$ of the testdata, $k = 1$.

For another $20\%$ of the testdata, $x \leq 100$.

For another $20\%$ of the testdata, $k = 2$.

For $100\%$ of the testdata, $1 \leq x \leq 10^9, 1 \leq k \leq 10^3$.

Credit: https://www.luogu.org/discuss/show/38908

Translated by ChatGPT 5