解方程

时间限制：$1$ 秒。内存限制：$512$ MB。

题目描述

有 $n$ 个未知整数 $x_1,x_2,\ldots,x_n$，每个数都在 $0$ 到 $2^B-1$ 之间。

现有 $m$ 条等式，每条等式包含四个整数 $u,v,k,c$，表示 $x_v-x_u\equiv c\pmod{2^k}$。不同等式的 $k$ 可以不同。当 $k=0$ 时，这条等式不对未知数施加限制。

判断是否存在一组整数，使所有等式同时成立。如果存在，输出任意一组满足要求的 $x_1,x_2,\ldots,x_n$。

输入格式

输入文件：equation.in。

第一行包含三个整数 $n,m,B$。

接下来 $m$ 行，每行包含四个整数 $u,v,k,c$，表示一条等式。

输出格式

输出文件：equation.out。

如果不存在满足要求的一组整数，输出一行 $\texttt{No}$。

否则，第一行输出 $\texttt{Yes}$，第二行输出 $n$ 个整数 $x_1,x_2,\ldots,x_n$。这些数必须在 $0$ 到 $2^B-1$ 之间，并满足全部等式。若有多组合法答案，输出任意一组即可。

样例

输入：

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

输出：

Yes
0 2 3

样例解释

取 $(x_1,x_2,x_3)=(0,2,3)$，三个差值依次为 $2,1,3$，分别满足模 $2,8,4$ 的要求。输出其他满足全部等式且取值合法的方案也会被接受。

附加样例 $\texttt{equation2.in/.ans}$、$\texttt{equation3.in/.ans}$、$\texttt{equation4.in/.ans}$、$\texttt{equation5.in/.ans}$ 分别满足测试点 $3\sim5$、$6\sim8$、$12\sim14$、$15\sim20$ 的限制。

数据范围

对于所有测试点，$1\le n\le2\times10^5$，$0\le m\le2\times10^5$，$1\le B\le60$，$1\le u,v\le n$，$0\le k\le B$，$0\le c<2^k$。允许自环与重复等式。

特殊性质 $A$：所有等式的 $k$ 均等于输入中的 $B$。

特殊性质 $B$：把每条等式视为连接 $u,v$ 的无向边，得到的图没有自环、重边和环，即为森林。

特殊性质 $C$：所有等式均满足 $u=1$。