23957번 - Sherlock and the Bit Strings 서브태스크다국어

Sherlock and Watson are playing a game involving bit strings, i.e., strings consisting only of the digits 0 and 1. Watson has challenged Sherlock to generate a bit string S of N characters S₁, S₂, ..., S_N. The string must obey each of K different constraints; each of these constraints is specified via three integers A_i, B_i, and C_i. The number of 1s in the substring S_Ai, S_{Ai + 1}, ..., S_Bi must be equal to C_i.

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 P^th in lexicographic order, with P counted starting from 1.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line containing three integers N, K, and P, as described above. Then, there are K more lines; the i-th of these contains three integers A_i, B_i and C_i, representing the parameters of the i-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 P^th lexicographically smallest bit string among all possible strings following the K specified constraints.

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 100.
• 1 ≤ K ≤ 100.
• 1 ≤ P ≤ min(10¹⁸, the number of bit strings that obey all of the constraints).
• 1 ≤ A_i ≤ B_i ≤ N for all 1 ≤ i ≤ K.
• 0 ≤ C_i ≤ N, for all 1 ≤ i ≤ K.
• (A_i, B_i) ≠ (A_j, B_j), for all 1 ≤ i < j ≤ K.

• A_i = B_i for all 1 ≤ i ≤ K.

• B_i - A_i ≤ 15 for all 1 ≤ i ≤ K.

Note that the last sample case would not appear in Small dataset.

In Sample Case #1, the bit strings that obey the only constraint in lexicographically increasing order are [010, 011, 110, 111].

In Sample Case #2, the bit strings that obey the given constraints in lexicographically increasing order are [0101, 1010].