Bulb Number

A switching box has (N) switches on top and (N) bulbs below. The switches are numbered (1,2,dots,N) from left to right. The bulbs are arranged from left to right as (B_N,B_{N-1},dots,B_1), so (B_1) is the rightmost bulb.

Each switch is connected to exactly one bulb by a wire. When several switches are pressed at the same time, a bulb turns on only if the wire connected to that bulb does not intersect any other wire whose switch is also pressed. If that wire intersects at least one other pressed wire, the bulb stays off.

If bulb (B_i) is on, bit (i) is 1; otherwise it is 0. The resulting (N)-bit binary number (B_NB_{N-1}dots B_1) is called a bulb number, and (B_1) is the least significant bit. Pressing no switches produces bulb number 0.

Given the connection structure of the switching box and an integer (K), sort every producible bulb number by its decimal value in increasing order. Find the (K)-th value. If fewer than (K) bulb numbers can be produced, output -1.

The first line contains the number of switches and bulbs, (N). (3 le N le 30)

The second line contains the switch numbers connected to bulbs (B_N,B_{N-1},dots,B_1), in that order, separated by spaces.

The third line contains the integer (K). (1 le K le 1,000,000,000)

Output the (K)-th producible bulb number when all producible values are sorted by decimal value in increasing order. If it does not exist, output -1.