SCALE - Funny scales


Kinh_Can has a set of precious weights P1, P2, ..., PN in which the mass of the ith weight is Pi = 3i-1, and a balance with 2 scales. On a nice day, Kinh_Can decided to show off his set of precious weights to his friends, and said that he can put them in equilibrium with any weight as long as its mass is not more than the mass of the sum of his weights. At first, his friends didn't believe, but after many trials they realized that Kinh_Can was right. In addition, while putting a thing whose mass is X on a scale, Kinh_Can could put right away the weights added on the 2 scales to keep their blance without any trial. With a random weight X (X is a natural number, X ≠ 0). Your task is to put weights on scales in order to keep the 2 scales' balance like Kinh_Can. The first scale initially weights X, and the second one weights 0.

Input

Input has exactly one line consisting 2 numbers, the first is N and the second is X.

Output

  • If there is no solution, you should write -1
  • If there is at least one solution for the problem, you should write exactly 2 lines:
    • The first line contains some numbers descripting the indices of the weights in the first disc
    • The second line contains some numbers description the indices of the weights in the second disc
    • Note: One of 2 lines can be blank

Constraints

  • 1 ≤ N ≤ 20
  • 1 ≤ X ≤ 2000000000

Example

Input 1:
10 2

Output 1:
1
2

Input 2:
10 5

Output 2:
1 2
3


hide comments
sieunhanbom04: 2016-08-04 11:08:14

I think this problem is purely solved by mathematics (Ternary numeral system).

Nic Roets: 2016-03-09 18:39:19

It looks like some inputs contain more than one line. Continue reading until EOF or n < 1 or x < 1

aghori_sadhu: 2015-10-19 19:49:51

Try these cases :
input : 20 11
output :
1
2 3
input : 20 4
output :
1 2

Last edit: 2015-10-19 21:35:22
Govind Lahoti: 2015-02-27 22:03:13

Beautiful problem...
Loved solving it

sriankit: 2013-07-18 08:05:01

awsum... :)

Trilok Sharma: 2013-06-24 13:57:03

Best Test case is :
i/p: 20 2000000000
o/p: -1

So,Assume N range 1 ≤ N ≤ 22 and take variables in long int,then
input:
22 2000000000
output:
1 5 7 8 9 19 20
2 6 10 12 13 15 16 17 21

Last edit: 2013-06-24 13:59:40
NodaR M JarraR: 2013-04-21 16:23:09

i am getting wa in the 19th running ,, what should be the problem? i think that i solved it correctly!!
does the spaces after the last number of output make a problem??

manish sharma: 2012-04-18 13:48:10

can there be more than 1 solution

cprocoder: 2011-07-28 03:21:24

Very nice problem

Sigma Kappa: 2011-04-30 09:31:04

The numbers should be output in increasing order.


Added by:nha.duong
Date:2007-07-29
Time limit:0.214s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Classical