AT_arc218_f2 [ARC218F2] Buckets

**F 和 F2 题的本质是同一道题，只是 $M$ 的限制不同。在 F2 题中，$M = 5$。** 给定一个正整数 $M$。对于以下问题： > **装水桶** > > 你有一个正整数 $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$ 的每一个 $i$，依次： - 对于 $j=0,1,\dots,M$ 的每一个 $j$，依次： - 重复 $X_{i,j}$ 次：在 $A$ 的末尾添加 $i$，在 $B$ 的末尾添加 $j$。 - 针对长度为 $N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}$ 的序列 $A$ 和 $B$，解决上面的“装水桶”问题。

输入由标准输入给出，格式如下： > $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`，否则输出 `No`。

### 样例解释 1 每次查询构造出的 $A$、$B$ 序列如下： - 第一次查询时：$A=(0,3,3),\ B=(0,1,5)$ - 第二次查询时：$A=(0,3,3,4),\ B=(0,1,5,0)$ - 第三次查询时：$A=(0,1,3,3,4),\ B=(0,5,1,5,0)$ ### 数据范围 - **$M = 5$** - $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 翻译