Description
在介绍十进制转二进制的篇目中,我们总会看到这样的方法:
- 求出这个数字除以 2 的商和余数,然后将余数写在右侧,用商替换原来的数字;
- 重复以上过程直到这个数字变为 0;
- 最后将右侧的所有余数倒序排列,得到的就是原数字的二进制形式。
Input
一行,一个正整数 n,表示她想要转成二进制的数字。
Output
输出若干行,每一行两个数字 xi 和 yi,表示第 i 次除法得到的商和余数。你应该保证 yi 是 0 或 1。
Sample Input Copy
9
Sample Output Copy
4 1
2 0
1 0
0 1
HINT
样例 1 解释
首先,9=2×4+1,所以第一行输出 4 1,并令 9 变为 4; 然后,4=2×2+0,所以第二行输出 2 0,并令 4 变为 2;
接着,2=2×1+0,所以第三行输出 1 0,并令 2 变为 1;
最后,1=2×0+1,所以第四行输出 0 1,并令 1 变为 0。过程结束。
数据范围
对于前 30% 的数据,保证 n 为若干个 2 的乘积,且 1≤n≤109;
对于另 30% 的数据,保证除法最多只进行 3 次;
对于 100% 的数据,保证 1≤n≤1018。