Sherlock과 비트 문자열

Sherlock과 Watson은 비트 문자열, 즉 숫자 0과 1만으로 이루어진 문자열을 사용하는 게임을 하고 있다. Watson은 Sherlock에게 N개의 문자 $S_{1}$, $S_{2}$, ..., $S_{N}$로 이루어진 비트 문자열 S를 만들라고 도전했다. 이 문자열은 서로 다른 K개의 제약 조건을 각각 충족해야 한다. 각 제약 조건은 세 정수 $A_{i}$, $B_{i}$, $C_{i}$로 지정된다. 부분 문자열 S_{$A_{i}$}, S_{$A_{i}$ + 1}, ..., S_{$B_{i}$}에 있는 1의 개수는 $C_{i}$와 같아야 한다.

Watson은 올바른 길이를 가지며 모든 제약 조건을 충족하는 문자열이 적어도 하나 존재하도록 제약 조건을 선택한다. 그러나 그러한 문자열이 여러 개일 수 있으므로, Watson은 Sherlock이 이 집합에서 사전식 순서로 $P^{th}$인 문자열을 선택하기를 원하며, P는 1부터 세기 시작한다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ N ≤ 100. 1 ≤ K ≤ 100. 1 ≤ P ≤ min($10^{18}$, 모든 제약 조건을 충족하는 비트 문자열의 개수). 모든 1 ≤ i ≤ K에 대해 1 ≤ $A_{i}$ ≤ $B_{i}$ ≤ N이다. 모든 1 ≤ i ≤ K에 대해 0 ≤ $C_{i}$ ≤ N이다. 모든 1 ≤ i < j ≤ K에 대해 ($A_{i}$, $B_{i}$) ≠ ($A_{j}$, $B_{j}$)이다.

작은 데이터 세트(테스트 세트 1 - 공개)

모든 1 ≤ i ≤ K에 대해 $A_{i}$ = $B_{i}$이다.

큰 데이터 세트(테스트 세트 2 - 비공개)

모든 1 ≤ i ≤ K에 대해 $B_{i}$ - $A_{i}$ ≤ 15이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 세 정수 N, K, P가 포함된 한 줄로 시작한다. 그다음 K개의 줄이 더 주어지며, 이 중 i번째 줄에는 위에서 설명한 i번째 제약 조건의 매개변수를 나타내는 세 정수 $A_{i}$, $B_{i}$, $C_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y이 포함된 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 지정된 K개의 제약 조건을 충족하는 가능한 모든 문자열 중 사전식 순서로 $P^{th}$번째로 작은 비트 문자열이다.

예제 케이스 #1에서 유일한 제약 조건을 충족하는 비트 문자열을 사전식 오름차순으로 나열하면 $[010, 011, 110, 111]$이다.

예제 케이스 #2에서 유일한 제약 조건을 충족하는 비트 문자열을 사전식 오름차순으로 나열하면 $[000, 001, 100, 101]$이다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 주어진 제약 조건을 충족하는 비트 문자열을 사전식 오름차순으로 나열하면 $[0101, 1010]$이다.