AT_arc218_f2.F2 - Buckets

Problems F and F2 are the same problem with different constraints on $M$. In Problem F2, $M = 5$.

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$ 的约束不同。在题目 F2 中，$M = 5$。

给定一个正整数 $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 sequences $A$ and $B$ obtained at each query are as follows:

• At the time of processing the first query: $A=(0,3,3),B=(0,1,5)$
• At the time of processing the second query: $A=(0,3,3,4),B=(0,1,5,0)$
• At the time of processing the third query: $A=(0,1,3,3,4),B=(0,5,1,5,0)$

Constraints

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

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