# 红石计算机

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 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

### 输入

```text
3 3 3
1 ^ 2 000
3 & 3 101
2 ^ 1 000
```

### 输出

```text
111
111
101
```

### 解释

取 $x_1=x_2=111$ 、$x_3=101$ 可满足所有关系，其他合法解也会被接受。

## 样例 2

### 输入

```text
2 2 3
1 | 2 111
1 & 2 000
```

### 输出

```text
000
111
```

### 解释

每一位上两个数恰有一个为一，所给方案满足要求。交换两个数也合法。

## 样例 3

### 输入

```text
1 1 1
1 ^ 1 1
```

### 输出

```text
No
```

### 解释

任何二进制数与自身异或都为零，因此这条关系无解。

## 样例 4

### 输入

```text
0 0 2
```

### 输出

```text

```

### 解释

没有未知数和关系，输出为空。

## 数据范围与保证

- $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% | 无额外条件 |