Under construction

Still being built. Things may change

Going Home

Interview

Time limit2sMemory limit1024 MB

Summary
Given buttons that OR-combine with the current universe number, find at most 100 presses that turn universe A into B, or report -1 if impossible.
Level

Medium4 of 10

Topics
Greedy, Bit manipulation
Solved
No attempts yet

Problem

After the collider exploded, Spider-Man Miles Morales ended up in a parallel universe. Realizing he needed help, he quickly found Peter Parker, the Spider-Man of this universe, and told him his story. After analyzing the collider blueprints Miles had accidentally taken with him and many other parameters, they found that Miles is in universe number AA and his own universe is number BB. After several months, they built a device for traveling between universes that can take Miles home. The device has nn buttons with numbers a1,a2,…,ana_1, a_2, \ldots, a_n. Pressing the button aia_i moves you from the current universe xx to universe x∨aix \lor a_i (∨\lor is bitwise OR). However, their resources were limited, so the device has enough charge for only 100100 moves. Miles and Peter are trying to work out the order in which to press the buttons to send Miles home. Help them!

Input

The first line contains three integers nn, AA, and BB: the number of buttons, the universe where Miles is now, and the universe where he needs to return (1≤n≤1051 \le n \le 10^5, 0≤A,B≤1090 \le A, B \le 10^9). The second line contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n, the numbers written on the buttons (1≤ai≤1091 \le a_i \le 10^9).

Output

If Miles cannot get home, print −1-1 on a single line. Otherwise, print the number kk of button presses on the first line (0≤k≤1000 \le k \le 100), and on the second line print the kk button numbers separated by spaces, in the order they should be pressed. If there are several answers, print any of them.

Hint

In the first example, press button 1 first to move from universe 2 to universe 2∨3=32 \lor 3 = 3. Then press button 4 to move from universe 3 to universe 3∨10=113 \lor 10 = 11.

Examples2

  1. Example 1

    Input
    4 2 11
    3 2 6 10
    
    Expected output
    2
    1 4
    
  2. Example 2

    Input
    4 4 11
    3 2 6 10
    
    Expected output
    -1