Background

Description

猴子吃桃问题就是：一个猴子，看到许多的桃子，第一天吃了一半，又吃了一个，第二天也吃了一半，又吃了一个，一直这样下去，到了第m天（输入），只剩下一个桃子了，求猴子吃桃子的过程，并倒序罗列每天吃完后的桃子数量（见输入和输出）

首先我们要知道怎么算

假设第一天猴子吃了n个，这么说就是n-(((n/2+1)/2+1)/2+1.../2+1)=1（重复m-1次因为猴子第一天已经吃了桃子）这样子倒推过来就是((1+1)*2+1)*2...+1)*2=n，第一天猴子吃了1个，我们赋值于x,x一直x=(x+1)*2重复m-1次就可以得出从第m天到第1天猴子吃桃的过程了。

Format

Input

Output

Samples

10

10:1
9:4
8:10
7:22
6:46
5:94
4:190
3:382
2:766
1:1534
1534

20

20:1
19:4
18:10
17:22
16:46
15:94
14:190
13:382
12:766
11:1534
10:3070
9:6142
8:12286
7:24574
6:49150
5:98302
4:196606
3:393214
2:786430
1:1572862
1572862

Limitation

1s, 1024KiB for each test case.