Under construction

Still being built. Things may change

The Number of Sequences

Time limit1sMemory limit128 MB

Summary
For a given N and C, find the lexicographically smallest triple (X, Y, Z) such that exactly C ordered N-tuples of 31-bit integers have OR X, AND Y, XOR Z, or report none exists.
Level

Hard9 of 10

Topics
Bit manipulation, Combinatorics, Math, Dynamic programming
Solved
No attempts yet

Problem

Consider a sequence of NN numbers that satisfies all four conditions below.

  1. Every number in the sequence is an integer between 00 and 231−12^{31} - 1, inclusive.
  2. The bitwise OR of every number in the sequence is XX.
  3. The bitwise AND of every number in the sequence is YY.
  4. The bitwise XOR of every number in the sequence is ZZ.

Taekhee owned every sequence that satisfies these conditions, but he lost some of them while moving. Once he knows XX, YY, and ZZ, he can build all of them again.

Taekhee remembers two facts. The sequence length is NN, and exactly CC sequences satisfy all four conditions.

Find the values of XX, YY, and ZZ. Two sequences whose numbers appear in a different order count as different sequences.

Input

The first line contains the sequence length NN and the number of sequences CC that satisfy the conditions, separated by a space. (1≤N≤1051 \le N \le 10^5, 0≤C≤10180 \le C \le 10^{18})

Output

On the first line print integers XX, YY, and ZZ between 00 and 231−12^{31} - 1, separated by spaces, for which exactly CC sequences satisfy the conditions.

If several triples (X,Y,Z)(X, Y, Z) satisfy the conditions, print the lexicographically smallest one. Take the smallest XX, among those the smallest YY, and among those the smallest ZZ.

If no such XX, YY, ZZ exist, print −1-1 and nothing else.

Examples2

  1. Example 1

    Input
    9 70110209207109375
    
    Expected output
    127 0 0
    
  2. Example 2

    Input
    100000 1000000000000000000
    
    Expected output
    -1