[语言月赛 202405] 二进制

在介绍十进制转二进制的篇目中，我们总会看到这样的方法： - 求出这个数字除以 $2$ 的**商**和**余数**，然后将余数写在右侧，用商替换原来的数字； - 重复以上过程直到这个数字变为 $0$； - 最后将右侧的所有余数**倒序**排列，得到的就是原数字的二进制形式。 小 S 也在学习二进制，不过她很懒，不想计算那么多次除法。于是她找到了你，希望你能为她写一个程序，帮助她得到上述过程中所有的**商**和**余数**。 ## Input 一行，一个正整数 $n$，表示她想要转成二进制的数字。 ## Output 输出若干行，每一行两个数字 $x_i$ 和 $y_i$，表示第 $i$ 次除法得到的商和余数。你应该保证 $y_i$ 是 $0$ 或 $1$。 [samples] ## Note ### 样例 1 解释 首先，$9 = 2 \times 4 + 1$，所以第一行输出 `4 1`，并令 $9$ 变为 $4$； 然后，$4 = 2 \times 2 + 0$，所以第二行输出 `2 0`，并令 $4$ 变为 $2$； 接着，$2 = 2 \times 1 + 0$，所以第三行输出 `1 0`，并令 $2$ 变为 $1$； 最后，$1 = 2 \times 0 + 1$，所以第四行输出 `0 1`，并令 $1$ 变为 $0$。过程结束。 ### 样例 2 解释 首先，$22 = 2 \times 11 + 0$，所以第一行输出 `11 0`，并令 $22$ 变为 $11$； 然后，$11 = 2 \times 5 + 1$，所以第二行输出 `5 1`，并令 $11$ 变为 $5$； 接着，$5 = 2 \times 2 + 1$，所以第三行输出 `2 1`，并令 $5$ 变为 $2$； 再然后，$2 = 2 \times 1 + 0$，所以第四行输出 `1 0`，并令 $2$ 变为 $1$； 最后，$1 = 2 \times 0 + 1$，所以第五行输出 `0 1`，并令 $1$ 变为 $0$。过程结束。 ### 数据范围 对于前 $30 \%$ 的数据，保证 $n$ 为若干个 $2$ 的乘积，且 $1 \leq n \leq 10^9$； 对于另 $30 \%$ 的数据，保证除法最多只进行 $3$ 次； 对于 $100 \%$ 的数据，保证 $1 \leq n \leq 10^{18}$。