#216665. [GKS 2018 #B] Sherlock and the Bit Strings

Sherlock and Watson are playing a game involving bit strings, i.e., strings consisting only of the digits and . Watson has challenged Sherlock to generate a bit string of characters , , ..., . The string must obey each of different constraints; each of these constraints is specified via three integers , , and . The number of s in the substring must be equal to .

Watson chooses the constraints in a way that guarantees that there is at least one string of the right length that obeys all of the constraints. However, since there could be multiple such strings, Watson wants Sherlock to choose the string from this set that is -th in lexicographic order, with counted starting from .

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with one line containing three integers , , and , as described above. Then, there are more lines; the -th of these contains three integers , and , representing the parameters of the -th constraint, as described above.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the th lexicographically smallest bit string among all possible strings following the specified constraints.

样例输入 1

2
3 1 2
2 2 1
3 1 1
2 2 0

样例输出 1

Case #1: 011
Case #2: 000

In Sample Case #1, the bit strings that obey the only constraint in lexicographically increasing order are .

In Sample Case #2, the bit strings that obey the only constraint in lexicographically increasing order are .

Limits

.

.

.

.

for all .

, for all .

, for all .

Small dataset (Test set 1 - Visible)

for all .

Large dataset (Test set 2 - hidden)

for all .