Problem Description

In the section about converting decimal to binary, we often see the following method:

• Calculate the quotient and remainder of the number divided by $2$, then write the remainder on the right and replace the original number with the quotient;
• Repeat the above process until the number becomes $0$;
• Finally, arrange all the remainders in reverse order to get the binary form of the original number.

Little S is also learning about binary, but she is lazy and doesn't want to perform so many divisions. So she has come to you, hoping you can write a program for her to help her get all the quotients and remainders in the above process.

Input Format

A single line containing a positive integer $n$, representing the number she wants to convert to binary.

Output Format

Output several lines, each line containing two numbers $x_i$ and $y_i$, representing the quotient and remainder of the $i$-th division. You should ensure that $y_i$ is either $0$ or $1$.

Sample Input and Output

Sample Input #1

9

Sample Output #1

4 1
2 0
1 0
0 1

Sample Input #2

22

Sample Output #2

11 0
5 1
2 1
1 0
0 1

Sample Input #3

1

Sample Output #3

0 1

Notes

Sample 1 Explanation

First, $9 = 2 \times 4 + 1$, so the first line outputs 4 1 and changes $9$ to $4$;
Then, $4 = 2 \times 2 + 0$, so the second line outputs 2 0 and changes $4$ to $2$;
Next, $2 = 2 \times 1 + 0$, so the third line outputs 1 0 and changes $2$ to $1$;
Finally, $1 = 2 \times 0 + 1$, so the fourth line outputs 0 1 and changes $1$ to $0$. The process ends.

Sample 2 Explanation

First, $22 = 2 \times 11 + 0$, so the first line outputs 11 0 and changes $22$ to $11$;
Then, $11 = 2 \times 5 + 1$, so the second line outputs 5 1 and changes $11$ to $5$;
Next, $5 = 2 \times 2 + 1$, so the third line outputs 2 1 and changes $5$ to $2$;
Then, $2 = 2 \times 1 + 0$, so the fourth line outputs 1 0 and changes $2$ to $1$;
Finally, $1 = 2 \times 0 + 1$, so the fifth line outputs 0 1 and changes $1$ to $0$. The process ends.

Data Range

For the first $30\%$ of the data, it is guaranteed that $n$ is a product of several $2$s, and $1 \leq n \leq 10^9$;
For the next $30\%$ of the data, it is guaranteed that the division is performed at most $3$ times;
For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 10^{18}$.

见题面 Input 部分

见题面 Output 部分