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 $ 以下です。 > > $ 1 $ から $ N $ の番号が付いた $ N $ 個のバケツがあります。全てのバケツには水が $ M $ L まで入ります。始め、バケツ $ i $ には $ A_i $ L の水が入っています。 > > あなたは以下の操作を好きな回数行うことが出来ます。 > > - 異なる $ 2 $ 個のバケツ $ i,j $ を選ぶ。以下の条件を両方満たしている間、バケツ $ i $ からバケツ $ j $ に水を移し続ける。 > - バケツ $ i $ にまだ水が残っている。 > - バケツ $ j $ に入っている水の量が $ M $ L 未満である。 > > あなたの目標は、全ての $ i $ についてバケツ $ i $ に水が $ B_i $ L 入っている状況にすることです。目標を達成することが出来るか判定してください。 $ M+1 $ 行 $ M+1 $ 列の非負整数行列 $ X=(X_{i,j})(0 \le i,j \le M) $ が与えられます。以下のクエリを $ Q $ 回処理してください。 - $ 0 \le i,j \le M $ を満たす非負整数 $ i,j,Y $ が与えられる。 $ X_{i,j} $ を $ Y $ に変更する。その後、以下の手順で非負整数列 $ A,B $ を得る。 - 非負整数列 $ A,B $ を空数列で初期化する。 - 以下を $ i = 0,1,\dots,M $ の順に行う。 - 以下を $ j = 0,1,\dots,M $ の順に行う。 - $ A $ の末尾に $ i $ を、 $ B $ の末尾に $ j $ を追加する操作を $ X_{i,j} $ 回行う。 - 長さ $ N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} $ の非負整数列 $ A,B $ について **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 $ 行目には $ \mathrm{query}_i $ において、目標を達成することが出来るならば `Yes` を、出来ないならば `No` を出力せよ。

### Sample Explanation 1 $ 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) $ になる。 $ 2 $ 番目のクエリによって、 $ 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) $ が得られます。 この場合、どのように操作をしても目標を達成することは出来ません。 $ 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) $ になる。 ### 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 $ - 入力は全て整数