/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
二次元のマス目における一番左上のマスの座標を (0, 0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i, j) とする。
N \times N マスの盤面がある。最初、盤面の各マス (i, j) に整数 a_{i, j} が設定されている。
3 \times 3 マスのスタンプが M 個ある。スタンプ m (0 \leq m \leq M - 1) の各マス (i, j) に整数 s_{m,i,j} が書かれている。
あなたは以下の操作を K 回まで行うことができる。
- スタンプ m と盤面のマス (p, q) (0 \leq p, q \leq N - 3) を選択し、スタンプ m の座標 (0, 0) が盤面のマス (p, q) と合うようにスタンプを押す。この操作により、スタンプの各マス (i, j) (0 \leq i, j \leq 2) に対して、盤面のマス (p + i, q + j) の値に s_{m,i,j} が加算される。盤面からはみ出るようにスタンプを押したり、スタンプを回転させて使用したりすることはできない。
同じスタンプを何度も使用したり、使わないスタンプがあったりしても構わない。同じ場所に何度もスタンプを押しても構わない。
最終的な盤面の各マスの値を 998244353 で割った余りの総和を最大化して欲しい。
得点
全ての操作を終えた後、盤面のマス (i, j) に設定された整数を b_{i, j} としたとき、以下の得点が得られる。
\[ \sum_{i = 0}^{N - 1}{\sum_{j = 0}^{N - 1}{(b_{i, j} \bmod 998244353)}} \]
ここで、 b_{i, j} \bmod 998244353 は b_{i, j} を 998244353 で割った余りを表す。
操作回数が K を超えた場合や、不正な操作を出力した場合は WA と判定される。
テストケースは全部で 150 個あり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
N M K
a_{0, 0} \cdots a_{0, N - 1}
\vdots
a_{N - 1, 0} \cdots a_{N - 1, N - 1}
s_{0, 0, 0} s_{0, 0, 1} s_{0, 0, 2}
s_{0, 1, 0} s_{0, 1, 1} s_{0, 1, 2}
s_{0, 2, 0} s_{0, 2, 1} s_{0, 2, 2}
\vdots
s_{M - 1, 0, 0} s_{M - 1, 0, 1} s_{M - 1, 0, 2}
s_{M - 1, 1, 0} s_{M - 1, 1, 1} s_{M - 1, 1, 2}
s_{M - 1, 2, 0} s_{M - 1, 2, 1} s_{M - 1, 2, 2}
各値はそれぞれ以下の制約を満たす。
- N = 9
- M = 20
- K = 81
- 0 \leq a_{i, j} \leq 998244352
- 0 \leq s_{m, i, j} \leq 998244352
出力
スタンプを押した回数を L (0 \leq L \leq K)、 l 回目の操作で選択したスタンプと盤面のマスをそれぞれ m_l (0 \leq m_l \leq M - 1) 、 (p_l, q_l) (0 \leq p_l, q_l \leq N - 3) としたとき、以下の形式で標準出力に出力せよ。
L
m_0 p_0 q_0
m_1 p_1 q_1
\vdots
m_{L - 1} p_{L - 1} q_{L - 1}
入力生成方法
L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L, U) と表す。
各 a_{i, j} と s_{m, i, j} は全て独立に、 a_{i, j} = \mathrm{rand}(0, 998244352), s_{m, i, j} = \mathrm{rand}(0, 998244352) により生成する。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
入力例 1
9 20 81 24323530 980293589 859258684 185499104 894688371 236405725 111530575 250271104 495624658 769596495 264300425 88876278 146578260 565437828 737999180 725732147 57726456 323844609 40096771 928203404 501627737 804865949 814572382 849529199 189832922 910184599 467494517 962420139 432607222 59818053 858072870 914485919 446805915 138548911 345246064 245004268 477044564 12166358 931360092 799278793 865992483 339109407 614502753 736626962 801948371 281576446 640350568 771040910 823574138 350308411 930294372 585808288 700370699 426021090 289960346 566527193 119082954 148354804 902944838 516738876 930961873 812731496 172242940 921564237 662077279 49476329 593121834 377147282 862136854 791213996 686329230 7403815 501340655 979965930 839183331 303883398 490179686 492481098 160122974 114672637 82049594 975741402 918762324 476374754 906657349 359110092 978536040 84599745 368692094 744129488 261705356 216870728 556481274 317767465 457532475 532110106 125703669 839188333 425571806 291667039 37052662 1276219 305291998 653050074 220563016 332525785 400712871 520185762 393148157 178758620 933441647 205044518 579917402 498932315 411369672 664953833 274696537 654712800 802006144 682742340 864455037 533661060 207561332 605472509 577911453 942938903 576270626 688256275 33493069 481710779 902547317 817131623 291465541 863597953 772086608 417987422 136453150 615090472 760882895 841541285 914039365 359505208 780663578 774735965 188919347 431579412 464452916 854985721 70294202 663019966 157776983 3557297 439447307 621014939 759908222 932643321 184225959 884108948 693640679 361651737 846036661 975413204 479224933 700946167 622558051 495003914 325785117 513339213 70238660 857642866 297571112 374937799 48000646 849682071 528095305 232520890 469018467 952599070 610262715 232403912 316958602 24859140 385411996 304561106 853230688 859071983 266806117 99442261 881952734 708824083 752081152 915353520 261135036 48934653 945657700 255395109 742827901 445178710 906120195 565840603 316740986 736297599 447489530 680619574 654670835 694926131 897183420 958993686 813942152 196144122 324334792 928014325 852381591 194958307 642660824 128931372 303306950 687790222 930130148 591510740 614681348 113389792 160195595 683240268 555351204 218729338 196609467 724290289 47413572 552092134 337674489 410209863 549012244 186533965 452647000 449090484 733453206 106059177 888943736 940915649 692940521 382797569 893532614 52383100 783583840 634565824 168433778 751831139 356971915 870682287 872212766 75893565 262231629 844472478 843213274 499286296 502562654 725538734 467780532 720085509 907848638
出力例 1
4 0 1 6 6 6 6 18 6 1 16 1 5
Problem Statement
In a two-dimensional grid, let (0, 0) be the coordinates of the top-left square, and (i, j) be the coordinates of the square located i squares down and j squares to the right from there.
There is an N \times N square board. Initially, each square (i, j) on the board is assigned an integer a_{i, j}.
There are M stamps, each with 3 \times 3 squares. On stamp m (0 \leq m \leq M - 1), an integer s_{m,i,j} is written in each square (i, j).
You can perform the following operation at most K times.
- Select a stamp m and a square (p, q) (0 \leq p, q \leq N - 3) on the board. Press the stamp in such a way that its coordinates (0, 0) align with the square (p, q) on the board. This operation increases the value of the square (p + i, q + j) on the board by s_{m,i,j} for each square (i, j) (0 \leq i, j \leq 2) on the stamp. You cannot press a stamp beyond the bounds of the board, nor can you rotate stamps.
You can use the same stamp multiple times or have stamps that are not used at all. It is also acceptable to press stamps multiple times on the same square.
Please maximize the sum of the remainders obtained by dividing the values of each square on the final board by 998244353.
Scoring
After performing all the operations, let b_{i, j} be the integer assigned to the square (i, j) on the board. Then, you will obtain the following score.
\[ \sum_{i = 0}^{N - 1}{\sum_{j = 0}^{N - 1}{(b_{i, j} \bmod 998244353)}} \]
Here, b_{i, j} \bmod 998244353 represents the remainder obtained by dividing b_{i, j} by 998244353.
If the number of operations exceeds K or if you output an illegal operation, the submission will be judged as WA.
There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.
Input
Input is given from Standard Input in the following format:
N M K
a_{0, 0} \cdots a_{0, N - 1}
\vdots
a_{N - 1, 0} \cdots a_{N - 1, N - 1}
s_{0, 0, 0} s_{0, 0, 1} s_{0, 0, 2}
s_{0, 1, 0} s_{0, 1, 1} s_{0, 1, 2}
s_{0, 2, 0} s_{0, 2, 1} s_{0, 2, 2}
\vdots
s_{M - 1, 0, 0} s_{M - 1, 0, 1} s_{M - 1, 0, 2}
s_{M - 1, 1, 0} s_{M - 1, 1, 1} s_{M - 1, 1, 2}
s_{M - 1, 2, 0} s_{M - 1, 2, 1} s_{M - 1, 2, 2}
Each value satisfies the following constraints.
- N = 9
- M = 20
- K = 81
- 0 \leq a_{i, j} \leq 998244352
- 0 \leq s_{m, i, j} \leq 998244352
Output
Let L (0 \leq L \leq K) be the number of operations, and m_l (0 \leq m_l \leq M - 1) and (p_l, q_l) (0 \leq p_l, q_l \leq N - 3) be the stamp and board square selected in the l-th operation, respectively. Then, output to Standard Output in the following format:
L
m_0 p_0 q_0
m_1 p_1 q_1
\vdots
m_{L - 1} p_{L - 1} q_{L - 1}
Input Generation
Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive.
Each a_{i, j} and s_{m, i, j} are all independently generated by a_{i, j} = \mathrm{rand}(0, 998244352) and s_{m, i, j} = \mathrm{rand}(0, 998244352).
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations.
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.
Sample Input 1
9 20 81 24323530 980293589 859258684 185499104 894688371 236405725 111530575 250271104 495624658 769596495 264300425 88876278 146578260 565437828 737999180 725732147 57726456 323844609 40096771 928203404 501627737 804865949 814572382 849529199 189832922 910184599 467494517 962420139 432607222 59818053 858072870 914485919 446805915 138548911 345246064 245004268 477044564 12166358 931360092 799278793 865992483 339109407 614502753 736626962 801948371 281576446 640350568 771040910 823574138 350308411 930294372 585808288 700370699 426021090 289960346 566527193 119082954 148354804 902944838 516738876 930961873 812731496 172242940 921564237 662077279 49476329 593121834 377147282 862136854 791213996 686329230 7403815 501340655 979965930 839183331 303883398 490179686 492481098 160122974 114672637 82049594 975741402 918762324 476374754 906657349 359110092 978536040 84599745 368692094 744129488 261705356 216870728 556481274 317767465 457532475 532110106 125703669 839188333 425571806 291667039 37052662 1276219 305291998 653050074 220563016 332525785 400712871 520185762 393148157 178758620 933441647 205044518 579917402 498932315 411369672 664953833 274696537 654712800 802006144 682742340 864455037 533661060 207561332 605472509 577911453 942938903 576270626 688256275 33493069 481710779 902547317 817131623 291465541 863597953 772086608 417987422 136453150 615090472 760882895 841541285 914039365 359505208 780663578 774735965 188919347 431579412 464452916 854985721 70294202 663019966 157776983 3557297 439447307 621014939 759908222 932643321 184225959 884108948 693640679 361651737 846036661 975413204 479224933 700946167 622558051 495003914 325785117 513339213 70238660 857642866 297571112 374937799 48000646 849682071 528095305 232520890 469018467 952599070 610262715 232403912 316958602 24859140 385411996 304561106 853230688 859071983 266806117 99442261 881952734 708824083 752081152 915353520 261135036 48934653 945657700 255395109 742827901 445178710 906120195 565840603 316740986 736297599 447489530 680619574 654670835 694926131 897183420 958993686 813942152 196144122 324334792 928014325 852381591 194958307 642660824 128931372 303306950 687790222 930130148 591510740 614681348 113389792 160195595 683240268 555351204 218729338 196609467 724290289 47413572 552092134 337674489 410209863 549012244 186533965 452647000 449090484 733453206 106059177 888943736 940915649 692940521 382797569 893532614 52383100 783583840 634565824 168433778 751831139 356971915 870682287 872212766 75893565 262231629 844472478 843213274 499286296 502562654 725538734 467780532 720085509 907848638
Sample Output 1
4 0 1 6 6 6 6 18 6 1 16 1 5