AT_arc218_f2 [ARC218F2] Buckets

**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 $ 以下です。 > > $ 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 それぞれのクエリ時点で得られる $ A,B $ は以下の通りです。 - $ 1 $ 番目のクエリを処理する時点では、 $ A=(0,3,3),B=(0,1,5) $ - $ 2 $ 番目のクエリを処理する時点では、 $ A=(0,3,3,4),B=(0,1,5,0) $ - $ 3 $ 番目のクエリを処理する時点では、 $ 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 $ - 入力は全て整数