Mobile Binary Number

A hanging mobile is made of horizontal bars and weights labeled 0 or 1. Under each bar, from left to right, there may be labels 0 and 1 or other horizontal bars.

Assume the mobile is always balanced. When wind blows, any horizontal bar may rotate, reversing the left-to-right order of everything hanging below that bar. Rotating different bars independently creates many possible states of the same mobile.

A state is written by the following rule. One horizontal bar is represented by one pair of parentheses. Inside the parentheses, write the labels and the representations of lower bars in their current left-to-right order. The whole representation always starts with an opening parenthesis and ends with a closing parenthesis.

For the state (10(1011)00(10(01))), deleting the parentheses and reading the labels from left to right gives the binary string 101011001001. If the middle (1011) bar rotates, the string can become 101101001001; if the top bar then rotates, the whole order is reversed and becomes 100100101101.

Any binary string obtainable from some state of the given mobile is called a mobile binary string. Different rotation states can produce the same binary string, so equal strings are counted only once.

For the mobile (0(1(01))1), the following states are part of what can occur.

• (0((01)1)1) -> 00111 -> the smallest string
• (0((10)1)1) -> 01011 -> the second smallest string
• (0(1(01))1) -> 01011 -> the same string as above
• (0(1(10))1) -> 01101 -> the third smallest string

Sort all distinct mobile binary strings in lexicographic order, which is the same as numeric order because all strings have the same length. Find the K-th string. If fewer than K distinct strings are obtainable, print NO.

The first line contains the current state representation of the mobile, made only of 0, 1, and parentheses, with no spaces. The total number of characters in the representation is at most 200. The second line contains the integer K, where 1 <= K <= 1,000. The input is always valid.

Print the K-th smallest mobile binary string on one line. If it does not exist, print NO. If the answer starts with 0, the leading zeroes must be printed as well.