시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB0000.000%

## 문제

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 S1, S2, ..., SN. The string must obey each of K different constraints; each of these constraints is specified via three integers Ai, Bi, and Ci. The number of 1s in the substring SAi, SAi + 1, ..., SBi must be equal to Ci.

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 Pth 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 Ai, Bi and Ci, 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 Pth 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(1018, the number of bit strings that obey all of the constraints).
• 1 ≤ AiBiN for all 1 ≤ i ≤ K.
• 0 ≤ CiN, for all 1 ≤ i ≤ K.
• (Ai, Bi) ≠ (Aj, Bj), for all 1 ≤ i < j ≤ K.

## Test Set 1 (11점)

• Ai = Bi for all 1 ≤ i ≤ K.

## Test Set 2 (26점)

• Bi - Ai ≤ 15 for all 1 ≤ i ≤ K.

## 예제 입력 1

2
3 1 2
2 2 1
4 3 1
1 2 1
2 3 1
3 4 1


## 예제 출력 1

Case #1: 011
Case #2: 0101


## 힌트

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].

## 채점 및 기타 정보

• 예제는 채점하지 않는다.