题目描述

Sherlock 和 Watson 正在玩一个涉及位串（即仅由数字 $0$ 和 $1$ 组成的字符串）的游戏。Watson 挑战 Sherlock 生成长度为 $N$ 的位串 $S$，其中 $S_1, S_2, \dots, S_N$ 需满足 $K$ 条不同的约束条件；每个约束条件通过三个整数 $A_i$、$B_i$ 和 $C_i$ 来指定。子串 $S_{A_i}, S_{A_i+1}, \dots, S_{B_i}$ 中 $1$ 的个数必须等于 $C_i$。

Watson 对约束条件的选择保证了至少存在一个符合所有约束条件的合法长度的字符串。然而，由于可能存在多个这样的字符串，Watson 希望 Sherlock 从该集合中选择字典序第 $P$ 小的字符串，其中 $P$ 从 $1$ 开始计数。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$K$ 和 $P$，含义如上所述。随后有 $K$ 行，其中第 $i$ 行包含三个整数 $A_i$、$B_i$ 和 $C_i$，表示第 $i$ 个约束条件的参数，如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在所有满足 $K$ 条约束条件的位串中字典序第 $P$ 小的位串。

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

Case #1: 011
Case #2: 000

提示

在样例 #1 中，满足唯一约束条件的位串按字典序递增排列为 $[010, 011, 110, 111]$。

在样例 #2 中，满足唯一约束条件的位串按字典序递增排列为 $[000, 001, 100, 101]$。

限制条件

$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) \neq (A_j, B_j)$。

小数据集（测试集 1 – 可见）

对于所有 $1 \le i \le K$，$A_i = B_i$。

大数据集（测试集 2 – 隐藏）

对于所有 $1 \le i \le K$，$B_i - A_i \le 15$。

翻译由 DeepSeek V4 Pro 完成