AT_ahc064_a [AHC064A] Non-Crossing Railcar Rearrangement

An urgent request has arrived from Takahashi Railway in the AtCoder Kingdom. They want your help rearranging the railcars in the freight terminal for the simultaneous departures the next morning. In the freight terminal, several tracks for departing trains (departure tracks) are lined up, and railcars are placed on them. In addition, the same number of tracks for temporarily storing railcars (siding tracks) are provided at the tail end of the departure tracks. By moving railcars appropriately between the departure tracks and the siding tracks, the goal is to arrange the railcars on each departure track in the prescribed order.  When performing multiple moves simultaneously, if the routes connecting departure tracks and siding tracks intersect, the railcars block each other's paths. Therefore, the moves performed at the same time must be chosen so that their routes do not intersect. For Takahashi Railway, arrange all railcars in the prescribed order in as few steps as possible.

There are $ R $ departure tracks arranged in the freight terminal, and $ R $ siding tracks are placed on the side opposite to the exits of the departure tracks. The departure tracks and the siding tracks are numbered $ 0,1,\ldots,R-1 $ from left to right. Hereafter, for a departure track, the end on the exit side is called the "front", and the opposite end is called the "rear". For a siding track, the end closer to the departure tracks is called the "front", and the opposite end is called the "rear". Every departure track is connected by rails to every siding track, and railcars can be moved between departure tracks and siding tracks. Each departure track has a capacity of 15 railcars, and each siding track has a capacity of 20 railcars. Any move that would exceed these capacities is prohibited. Initially, each departure track contains 10 railcars. Each railcar is assigned a unique ID from $ 0,\ldots,10R-1 $ , and the ID of the railcar placed at the $ c $ -th position from the front of departure track $ r $ is $ Y_{r,c} $ . All siding tracks are empty. By moving railcars between departure tracks and siding tracks, the goal is to arrange, for each departure track $ r $ , the railcars with IDs $ 10r, 10r+1, \ldots, 10r+9 $ in this order from the front. In each turn, you may perform **multiple moves simultaneously** from the following two types of moves. Each move handles $ k $ consecutive railcars ( $ k \ge 1 $ ), and their order is preserved. - (type = 0) Take $ k $ consecutive railcars from the rear of departure track $ i $ and attach them to the front of siding track $ j $ . - (type = 1) Take $ k $ consecutive railcars from the front of siding track $ j $ and attach them to the rear of departure track $ i $ .  To ensure safe train operations, the moves performed in the same turn must be chosen so that their routes do not intersect, regardless of direction. That is, the following two conditions must be satisfied. - A departure track or siding track must not be used more than once in the same turn. - If a move between departure track $ i_1 $ and siding track $ j_1 $ , and a move between departure track $ i_2 $ and siding track $ j_2 $ are performed simultaneously, then if $ i_1 < i_2 $ , it must hold that $ j_1 < j_2 $ . You may perform at most 4000 turns of moves.

The input is given from Standard Input in the following format: > $ R $ $ Y_{0,0} $ $ \cdots $ $ Y_{0,9} $ $ \vdots $ $ Y_{R-1,0} $ $ \cdots $ $ Y_{R-1,9} $ - In every test case, $ R = 10 $ . - $ Y_{r,c} $ is the ID of the railcar placed at the $ c $ -th position from the front of departure track $ r $ in the initial state ( $ 0 \leq c < 10 $ ). - $ Y_{r,c} $ contains each of $ 0,\ldots,10R-1 $ exactly once.

Print the sequence of moves to Standard Output in the following format: > $ T $ $ K_0 $ $ \mathrm{type} $ $ i $ $ j $ $ k $ $ \vdots $ $ \mathrm{type} $ $ i $ $ j $ $ k $ $ \vdots $ $ K_{T-1} $ $ \mathrm{type} $ $ i $ $ j $ $ k $ $ \vdots $ $ \mathrm{type} $ $ i $ $ j $ $ k $ Here, $ T $ is the number of turns in which moves are performed ( $ T \leq 4000 $ ). After printing $ T $ , for each turn $ t = 0, 1, \cdots, T-1 $ , print the following in this order. - First, print the number of moves performed in that turn, $ K_t $ , on a single line ( $ 1 \leq K_t \leq R $ ). - Then, print each of the moves performed in that turn on the following $ K_t $ lines in the format `type i j k` ( $ \mathrm{type} \in \{0,1\} $ , $ 0 \leq i,j < R $ , $ k \geq 1 $ ). - If $ \mathrm{type} = 0 $ , take $ k $ railcars from the rear of departure track $ i $ and attach them to the front of siding track $ j $ . - If $ \mathrm{type} = 1 $ , take $ k $ railcars from the front of siding track $ j $ and attach them to the rear of departure track $ i $ . [Show example](https://img.atcoder.jp/ahc064/fLqO0Ras.html?lang=en&seed=0&output=sample)

### Scoring Let $ T $ be the number of turns in the output sequence of moves. If all departure tracks exactly match the target configuration, the score is $ 100R + 4000 - T $ . Otherwise, the score is the sum of the following points over each railcar placed on the departure tracks in the final state (at most $ 10R $ railcars). - 1 point if the railcar is placed on the correct departure track - An additional 9 points if its position from the front is also correct If the number of turns exceeds 4000, or if the output violates the non-intersection constraint or the capacity constraint of any track, the submission is 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 , and the score of the submission will be zero. 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 Generation In every test case, $ R = 10 $ . Generate a uniformly random permutation of the integer sequence $ 0,1,\ldots,10R-1 $ , and assign the elements in order to $ Y_{0,0}, Y_{0,1}, \ldots, Y_{0,9}, Y_{1,0}, \ldots, Y_{R-1,9} $ . ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc064/fLqO0Ras.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc064/fLqO0Ras.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc064/fLqO0Ras_windows.zip): 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.