AT_arc218_f2 [ARC218F2] 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} $ .

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 $

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

### Sample Explanation 1 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.