AT_arc218_f.Buckets

Problems F and F2 are the same problem with different constraints on $M$. In Problem F, $1 \le M \le 4$.

You are given a positive integer $M$. Consider the following problem.

Bucket

You are given a positive integer $N$ and non-negative integer sequences $A=(A_1,A_2,\dots,A_N)$ and $B=(B_1,B_2,\dots,B_N)$ of length $N$. All elements of $A$ and $B$ are between $0$ and $M$, inclusive.

There are $N$ buckets numbered $1$ to $N$. Each bucket can hold up to $M$ liters of water. Initially, bucket $i$ contains $A_i$ liters of water.

You may perform the following operation any number of times.

• Choose two distinct buckets $i$ and $j$. Continue pouring water from bucket $i$ into bucket $j$ as long as both of the following conditions are satisfied:
  • Bucket $i$ still has water remaining.
  • The amount of water in bucket $j$ is less than $M$ liters.

Your goal is to have exactly $B_i$ liters of water in bucket $i$ for all $i$. Determine whether the goal can be achieved.

You are given a non-negative integer matrix $X=(X_{i,j})(0 \le i,j \le M)$ of $(M+1)$ rows and $(M+1)$ columns. Process the following queries $Q$ times.

• You are given non-negative integers $i,j,Y$ with $0 \le i,j \le M$. Change $X_{i,j}$ to $Y$. Then, obtain non-negative integer sequences $A$ and $B$ by the following procedure.

  • Initialize non-negative integer sequences $A$ and $B$ as empty sequences.

  • For $i = 0,1,\dots,M$ in this order:

  • For $j = 0,1,\dots,M$ in this order:

  • Do this $X_{i,j}$ times: append $i$ to the end of $A$ and $j$ to the end of $B$.

• Solve Bucket for the non-negative integer sequences $A$ and $B$ of length $N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}$.

题目 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$（含端点）之间。

有 $N$ 个编号为 $1$ 至 $N$ 的水桶。每个水桶最多可容纳 $M$ 升水。初始时，第 $i$ 个水桶中含有 $A_i$ 升水。

你可以执行以下操作任意多次：

• 选择两个不同的水桶 $i$ 和 $j$，并持续将水从水桶 $i$ 倒入水桶 $j$，直到满足以下任一条件为止：
  • 水桶 $i$ 中已无剩余水量；
  • 水桶 $j$ 中的水量已达 $M$ 升。

你的目标是使得对每个 $i$，第 $i$ 个水桶中恰好含有 $B_i$ 升水。请判断该目标是否可达。

给定一个 $(M+1) \times (M+1)$ 的非负整数矩阵 $X = (X_{i,j})$（其中 $0 \le i,j \le M$）。你需要处理 $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$ 的顺序遍历；
*   对每一对 $(i,j)$，重复 $X_{i,j}$ 次：将 $i$ 追加到序列 $A$ 末尾，同时将 $j$ 追加到序列 $B$ 末尾。

• 针对由此生成的、长度为 $N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}$ 的非负整数序列 $A$ 和 $B$，求解上述 水桶问题（Bucket）。

The input is given from Standard Input in the following format:

$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$

Each query is given in the following format:

$i\ j\ Y$

输入从标准输入中按以下格式给出：

$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$

Output $Q$ lines. The $i$-th line should contain Yes if the goal can be achieved in $\mathrm{query}_i$, and No otherwise.

输出 $Q$ 行。第 $i$ 行应包含 Yes（如果在 $\mathrm{query}_i$ 中可以达成目标），否则包含 No。

Sample 1 Explanation:
The first query makes $X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$, and we obtain $A=(1,1,2),B=(2,2,0)$.

In this case, the goal can be achieved by the following sequence of operations, for example.

• Set $i = 1,j = 2$. The amount of water in each bucket changes from $(1,1,2)$ to $(0,2,2)$.
• Set $i = 3,j = 1$. The amount of water in each bucket changes from $(0,2,2)$ to $(2,2,0)$.

The second query makes $X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$, and we obtain $A=(1,1,2,2),B=(2,2,0,3)$.

In this case, the goal cannot be achieved no matter how operations are performed.

The third query makes $X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$, and we obtain $A=(1,1,2,2,2),B=(2,2,0,1,3)$.

In this case, the goal can be achieved by the following sequence of operations, for example.

• Set $i = 1,j = 2$. The amount of water in each bucket changes from $(1,1,2,2,2)$ to $(0,2,2,2,2)$.
• Set $i = 3,j = 1$. The amount of water in each bucket changes from $(0,2,2,2,2)$ to $(2,2,0,2,2)$.
• Set $i = 4,j = 5$. The amount of water in each bucket changes from $(2,2,0,2,2)$ to $(2,2,0,1,3)$.

Constraints

• $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$ at any time.
• All input values are integers.

样例 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$。
• 所有输入值均为整数。