셜록과 비트 문자열

셜록과 왓슨은 0과 1로만 이루어진 비트 문자열을 이용한 게임을 하고 있다. 왓슨은 셜록에게 길이가 N인 비트 문자열 S, 즉 S_1, S_2, ..., S_N을 만들라고 한다. 문자열은 K개의 제약 조건을 모두 만족해야 한다. 각 제약 조건은 정수 A_i, B_i, C_i로 주어지며, 부분 문자열 S_{A_i}, S_{A_i+1}, ..., S_{B_i}에 포함된 1의 개수는 C_i와 같아야 한다. 왓슨은 올바른 길이의 문자열이 최소 하나는 모든 제약을 만족하도록 제약 조건을 고른다. 조건을 만족하는 문자열이 여러 개일 수 있으므로, 왓슨은 그중 사전순으로 P번째에 오는 문자열을 출력하라고 한다. P는 1부터 센다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 정수 N, K, P가 주어지는 한 줄로 시작한다. 이어서 K개의 줄이 주어지며, i번째 줄에는 정수 A_i, B_i, C_i가 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 K개의 제약을 모두 만족하는 비트 문자열 중 사전순으로 P번째인 문자열이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 주어진 K개의 제약을 만족하는 모든 문자열 중 사전순으로 P번째인 비트 문자열이다.

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le K \le 100$
• $1 \le P \le \min(10^{18}, \text{모든 제약을 만족하는 비트 문자열의 개수})$
• 모든 $1 \le i \le K$에 대해 $1 \le A_i \le B_i \le N$
• 모든 $1 \le i \le K$에 대해 $0 \le C_i \le N$
• 모든 $1 \le i < j \le K$에 대해 $(A_i, B_i) \ne (A_j, B_j)$

마지막 샘플 케이스는 Small 데이터셋에는 나오지 않는다.

샘플 케이스 1에서 유일한 제약을 만족하는 비트 문자열은 사전순으로 [010, 011, 110, 111]이다.

샘플 케이스 2에서 주어진 제약을 만족하는 비트 문자열은 사전순으로 [0101, 1010]이다.