红石计算机¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB
背景故事¶
村长制作的红石计算机仍在调试中。为了检查记录的运算结果是否相互一致，他想找出一组能够产生全部记录结果的输入；若不存在，也需要明确报告。
形式化问题描述¶
有 \(n\) 个未知的 \(k\) 位二进制数 \(x_1,\ldots,x_n\) .给定 \(m\) 条关系，每条形如
\[
x_a\mathbin{\mathrm{op}}x_b=C
\]
其中运算符为按位异或 ^ 、按位与 & 或按位或 | ，\(C\) 是给定的 \(k\) 位二进制数。允许 \(a=b\) ，也允许重复或矛盾的关系。
构造一组同时满足所有关系的 \(x_i\) ；有多组解时输出任意一组。不存在解时输出 No .所有二进制串均按最高位到最低位书写，允许前导零。
输入格式¶
第一行三个整数 \(n,m,k\) .接下来 \(m\) 行，每行依次给出 \(a,\mathrm{op},b,C\) ，各项以空格分隔。
输出格式¶
若无解，输出一行 No .否则输出 \(n\) 行，每行恰好 \(k\) 个字符 0 或 1 ，第 \(i\) 行表示 \(x_i\) .
当 \(n=0\) 时必有 \(m=0\) ，空赋值满足全部关系，此时输出为空。评测接受任意合法解，忽略空白分隔符，但不允许额外的非空白内容。
样例 1¶
输入¶
3 3 3
1 ^ 2 000
3 & 3 101
2 ^ 1 000
输出¶
111
111
101
解释¶
取 \(x_1=x_2=111\) 、\(x_3=101\) 可满足所有关系，其他合法解也会被接受。
样例 2¶
输入¶
2 2 3
1 | 2 111
1 & 2 000
输出¶
000
111
解释¶
每一位上两个数恰有一个为一，所给方案满足要求。交换两个数也合法。
样例 3¶
输入¶
1 1 1
1 ^ 1 1
输出¶
No
解释¶
任何二进制数与自身异或都为零，因此这条关系无解。
样例 4¶
输入¶
0 0 2
输出¶
解释¶
没有未知数和关系，输出为空。
数据范围与保证¶
- \(0\le n\le500\) ，\(0\le m\le10000\) ，\(1\le k\le150\) .
- 每条关系满足 \(1\le a,b\le n\) ，\(C\) 恰好包含 \(k\) 个二进制字符。
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 10% | \(k=1\) ，\(n\le20\) |
| 20% | \(k=1\) ，\(n\le50\) |
| 70% | 无额外条件 |