Codeforces 618 . A Slime Combining

A - Slime Combining

Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit  Status  Practice  CodeForces 618A

Description

Your friend recently gave you some slimes for your birthday. You have n slimes all initially with value 1.

You are going to play a game with these slimes. Initially, you put a single slime by itself in a row. Then, you will add the other n - 1slimes one by one. When you add a slime, you place it at the right of all already placed slimes. Then, while the last two slimes in the row have the same value v, you combine them together to create a slime with value v + 1.

You would like to see what the final state of the row is after you've added all n slimes. Please print the values of the slimes in the row from left to right.

Input

The first line of the input will contain a single integer, n (1 ≤ n ≤ 100 000).

Output

Output a single line with k integers, where k is the number of slimes in the row after you've finished the procedure described in the problem statement. The i-th of these numbers should be the value of the i-th slime from the left.

Sample Input

Input

1

Output

1

Input

2

Output

2

Input

3

Output

2 1

Input

8

Output

4

Hint

In the first sample, we only have a single slime with value 1. The final state of the board is just a single slime with value 1.

In the second sample, we perform the following steps:

Initially we place a single slime in a row by itself. Thus, row is initially 1.

Then, we will add another slime. The row is now 1 1. Since two rightmost slimes have the same values, we should replace these slimes with one with value 2. Thus, the final state of the board is 2.

In the third sample, after adding the first two slimes, our row is 2. After adding one more slime, the row becomes 2 1.

In the last sample, the steps look as follows:

1. 1
2. 2
3. 2 1
4. 3
5. 3 1
6. 3 2
7. 3 2 1
8. 4

    该题题目挺容易理解，每次放一个一在末尾。若末尾两数相等则倒数第二个数加一，末尾数清零，要求打印剩余的数。模拟一下即可求解。

    另外该题还可通过观察数组的规律进行求解，代码书写非常简洁，另辟蹊径，见AC代码：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

int main()
{
	int n;
	cin>>n;
	vector <int> a;
	int res=1;
	while(n)
	{
		if(n%2)
			a.push_back(res);
		res++;
		n/=2;
	}
	for(int i=a.size()-1; i>0; i--)
		printf("%d ",a[i]);
	printf("%d\n",a[0]);
	return 0;
}

   在模拟过程复杂的情况下找规律不失为一个很好的选择。

   特记下，以备后日回顾。