Baby Goat Lineup

Baby goats are standing in line for dinner. Each goat wears a binary label made only of 0 and 1, and every label has length at most 31 bits.

They do not line up in the usual increasing binary order 0, 1, 10, 11, 100, .... Instead, they use the following priority rules.

• A goat whose label contains fewer 1 bits stands earlier.
• If two labels contain the same number of 1 bits, the smaller binary value stands earlier.

For instance, 1000 comes before 110 because 1000 has one 1 bit and 110 has two. If all labels from 100 through 1111 are ordered by this rule, the order is as follows.

100, 1000, 101, 110, 1001, 1010, 1100, 111, 1011, 1101, 1110, 1111

Except for the label exactly equal to 0, no label may start with 0.

Given all goats with labels from A through B, find the label of the X-th goat after sorting by the priority rules above.

The first line contains A.

The second line contains B.

The third line contains the position X of the goat to find. The first goat has position 1.

Print the label of the goat at that position.