Secret Message

Limits: 4 sec., 1024 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka are performing a secret, but very important task. Unfortunately, they cannot tell us any more details. Right now, our heroes are preparing a secret message for Malyuk, which needs to be encoded in binary format and sent over the network.

The entire text contains \(n\) distinct words. For convenience, Zenyk numbered them from 1 to \(n\). The words appear in the text \(c_1, c_2, \ldots, c_n\) times, respectively. For each word, Marichka wants to determine a code consisting of zeros and ones. She considers an encoding acceptable under the following conditions:

• the length of the code for each word is at least \(a\) and at most \(b\);

• all word codes are distinct;

• no code is a prefix of another code.

To generate the encoded message, Zenyk sequentially writes down the codes of the words as they appear in the text, without any separators between them. Since we want to minimize the transmission time over the network, the length of the encoded message should be as small as possible. Help Zenyk and Marichka choose among all acceptable encodings the one that allows generating the shortest possible encoded text.

Input

The first line contains three space-separated integers \(n\), \(a\), and \(b\). The next line contains \(n\) space-separated integers \(c_i\).

Output

Output \(n\) lines with the word encodings. Line \(i\) should contain the encoding for the \(i\)-th word. The encoding must be acceptable, and the corresponding encoded text must be one of the shortest. If there are multiple optimal encodings, output any of them. If no acceptable encoding exists, output -1 instead.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a \le b \le 100\),

\(1 \le c_i \le 10^{18}\).

Samples