题目描述

众所周知，小葱同学擅长计算，尤其擅长计算组合数，所以小葱给了你两个数 $x$ 和 $k$，希望你把 $x$ 分成恰好 $k$ 个不同的组合数的和。所谓不同，即对于两个组合数 $C(n_1,m_1)$ 和 $C(n_2,m_2)$，如果 $n_1\neq n_2$ 或者 $m_1\neq m_2$，我们就称这两个组合数是不同的。为了使得计算不过于复杂，你需要保证你给出的任何一个组合数 $C(n,m)$ 满足 $0\leq m\leq n\leq x$。数据保证一定有解。

输入格式

从标准输入读入数据。

第一行两个整数 $x,k$。

输出格式

输出到标准输出。

$k$ 行，每行两个整数 $n,m$ 代表一个组合数 $C(n,m)$。如果有多种可能的答案，任意输出一组即可。

样例

input

6 2

output

3 1
3 2

数据范围与提示

对于 $20\%$ 的数据，$k=1$。

对于另外 $20\%$ 的数据，$x\leq 100$。

对于另外 $20\%$ 的数据，$k=2$。

对于 $100\%$ 的数据，$1\leq x\leq 10^9,1\leq k\leq 10^3$。

来自 CodePlus 第 4 次月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea 与命题/钟皓曦　验题/何昊天
Git Repo：https://git.thusaac.org/publish/CodePlus4
感谢腾讯公司对此次比赛的支持。