1001. xyz 问题

题目描述

河灵和胖胖龙正在玩一款逻辑推理类游戏。游戏桌上摆放着 n 张数字牌 x1, x2, …, xn，其中 xi 表示第 i 张数字

牌上的数字，每张数字牌上只能填写数字 0 或 1。桌上还摆放着 m 张运算牌 op1, op2, …, opm，其中 opj 表示第 j 张运

算牌上的运算符，每张运算牌上只能填写以下三种运算符之一：

• &：按位与。

• |：按位或。

• ^：按位异或。

现在，胖胖龙向河灵发起了挑战。他给出了 k 个条件，其中每个条件都包含四个整数 i, j, y, z (1 ≤ i ≤

n, 1 ≤ j ≤ m, 0 ≤ y, z ≤ 1)，表示河灵的填写结果需要满足等式xi opj y = z

请你帮帮河灵，为每张数字牌填写 0 或 1，并为每张运算牌填写 &, |,^ 的其中一种，使得填写方案满足胖胖龙给出的所有条件。或判断不

存在满足条件的填写方案。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 5 × 104 )，表示数据组数。对于每组测试数据：第一行三个正整数 n, m, k (1 ≤ n, m, k ≤ 3 × 105 )，分别表示数字牌个数、运算牌个数以及条件个数。

接下来 k 行，每行四个整数 i, j, y, z (1 ≤ i ≤ n, 1 ≤ j ≤ m, 0 ≤

y, z ≤ 1)，表示河灵的填写结果需要满足等式 xi opj y = z。

一张数字牌或运算牌可以不出现在任何条件中；同一张数字牌或运算牌可能同时出现在多个条件中。保证所有测试数据中 n 之和、m 之和与 k 之和均不超过 2 × 106。

输出格式

对于每组测试数据：若存在满足条件的填写方案，输出的第一行包含一个字符串 YES。第二行输出一个长度为 n 的 01 串，其中第 i 个字符表示第 i 张数字牌上的数字 xi。

第三行输出一个长度为 m 的字符串，其中第 j 个字符表示第 j 张运算牌上的运算符 opj，字符只能是 &, |, ^ 的其中一种。

若存在多种满足条件的填写方案，输出任意一种即可。若不存在满足条件的填写方案，输出一行一个字符串 NO。

样例输入

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

样例输出

YES
011
&^
NO

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）