AT_arc218_f [ARC218F] Buckets

**问题 F 和 F2 是同一个问题，只是在 $M$ 上有不同的限制。在问题 F 中，$1 \le M \le 4$。** 给定一个正整数 $M$。我们考虑如下问题： > **Bucket（倒水）** 给定一个正整数 $N$ 和两个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$ 和 $B=(B_1,B_2,\dots,B_N)$。所有 $A$ 和 $B$ 的元素都在 $0$ 到 $M$ 之间（包含 $0$ 和 $M$）。 > > 有 $N$ 个编号为 $1$ 到 $N$ 的水桶。每个水桶最多可容纳 $M$ 升水。最初，第 $i$ 个水桶有 $A_i$ 升水。 > > 你可以任意多次进行以下操作： > > - 选择两个不同的水桶 $i$ 和 $j$。只要同时满足以下两个条件，就不断把 $i$ 号桶的水倒入 $j$ 号桶： > - $i$ 号桶还有剩余的水； > - $j$ 号桶中的水量还不足 $M$ 升。 > > 你的目标是让每个水桶 $i$ 恰好有 $B_i$ 升水。请判断目标是否能达成。 现在你有一个非负整数矩阵 $X=(X_{i,j})$，下标范围 $0 \le i,j \le M$，共 $(M+1)$ 行 $(M+1)$ 列。处理以下 $Q$ 个询问。 - 给定非负整数 $i,j,Y$，其中 $0 \le i,j \le M$。将 $X_{i,j}$ 变为 $Y$。然后通过以下过程获得非负整数序列 $A$ 和 $B$： - 将 $A$ 和 $B$ 初始化为空序列。 - 对 $i=0,1,\dots,M$ 依次进行： - 对 $j=0,1,\dots,M$ 依次进行： - 重复 $X_{i,j}$ 次：将 $i$ 添加到 $A$ 的末尾，将 $j$ 添加到 $B$ 的末尾。 - 对于 $A$ 和 $B$（长度为 $N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}$），解决 **Bucket** 问题。

输入从标准输入读取，格式如下： > $M \ Q$ > $X_{0,0}\ X_{0,1}\ \dots\ X_{0,M}$ > $X_{1,0}\ X_{1,1}\ \dots\ X_{1,M}$ > $\vdots$ > $X_{M,0}\ X_{M,1}\ \dots\ X_{M,M}$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个询问的格式如下： > $i\ j\ Y$

输出 $Q$ 行。第 $i$ 行输出 `Yes`，如果第 $i$ 次询问可以达成目标，否则输出 `No`。

### 样例解释 1 第一次询问后，$X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$，得到 $A=(1,1,2),B=(2,2,0)$。 此时，可以通过如下操作之一实现目标： - 选 $i=1,j=2$，每个桶的水量由 $(1,1,2)$ 变为 $(0,2,2)$。 - 选 $i=3,j=1$，水量由 $(0,2,2)$ 变为 $(2,2,0)$。 第二次询问后，$X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$，得到 $A=(1,1,2,2),B=(2,2,0,3)$。 此时无论如何操作都无法达成目标。 第三次询问后，$X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$，得到 $A=(1,1,2,2,2),B=(2,2,0,1,3)$。 此时，可以通过如下操作之一实现目标： - 选 $i=1,j=2$，水量由 $(1,1,2,2,2)$ 变为 $(0,2,2,2,2)$。 - 选 $i=3,j=1$，水量由 $(0,2,2,2,2)$ 变为 $(2,2,0,2,2)$。 - 选 $i=4,j=5$，水量由 $(2,2,0,2,2)$ 变为 $(2,2,0,1,3)$。 ### 数据范围 - **$1 \le M \le 4$** - $1 \le Q \le 10^6$ - $0 \le X_{i,j},Y \le 10^{17}$ - $0 \le i,j \le M$ - 任意时刻均有 $\sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1$ - 输入中的所有数均为整数。 由 ChatGPT 5 翻译