AT_ahc065_a [AHC065A] Conveyor Design

AtCoder Inc. has recently introduced a new warehouse to store its original merchandise sold online. The warehouse contains a large number of boxes holding items such as T-shirts, keychains, and acrylic stands, and each box is assigned a management number. Since the boxes were brought in hastily, they were placed in locations completely unrelated to their numbers. For future inventory management, the boxes need to be taken out through the exit in increasing order of management number. CEO Takahashi decided to install a circular conveyor belt in the warehouse and make the boxes circulate so that all boxes can be taken out with as few operations as possible.

There is an $ N\times N $ warehouse. Let $ (0,0) $ be the coordinates of the top-left cell, and let $ (i,j) $ be the coordinates of the cell located $ i $ cells downward and $ j $ cells to the right from there. The cell $ (0,N/2) $ contains the exit of the warehouse. There is exactly one box with each number from $ 0 $ to $ N^2-1 $ in the warehouse. In the initial state, the number of the box placed in cell $ (i,j) $ is $ a_{i,j} $ . First, install at most $ N^2 $ loop-shaped devices in the warehouse. Hereafter, each loop-shaped device is called a **conveyor belt**. The $ m $ -th conveyor belt is represented by a sequence of cells \\\[ (i\_{m,0},j\_{m,0}), (i\_{m,1},j\_{m,1}), \\ldots, (i\_{m,l\_m-1},j\_{m,l\_m-1}) \\\] where $ l_m $ is the length of the conveyor belt. Each conveyor belt must satisfy the following conditions. - $ l_m\geq 2 $ . - For each $ x=0,\ldots,l_m-1 $ , $ 0\leq i_{m,x},j_{m,x}

Input is given from Standard Input in the following format. > $ N $ $ a_{0,0} $ $ \cdots $ $ a_{0,N-1} $ $ \vdots $ $ a_{N-1,0} $ $ \cdots $ $ a_{N-1,N-1} $ - In all test cases, $ N $ is fixed to $ 20 $ . - $ a_{i,j} $ represents the number of the box placed in cell $ (i,j) $ in the initial state. - $ a_{i,j} $ is an integer satisfying $ 0\leq a_{i,j}\leq N^2-1 $ . - The array $ a $ contains each integer from $ 0 $ to $ N^2-1 $ exactly once.

First, let $ M $ be the number of conveyor belts to install, and output it to Standard Output in the following format. > $ M $ $ l_0 $ $ i_{0,0} $ $ j_{0,0} $ $ \cdots $ $ i_{0,l_0-1} $ $ j_{0,l_0-1} $ $ \vdots $ $ l_{M-1} $ $ i_{M-1,0} $ $ j_{M-1,0} $ $ \cdots $ $ i_{M-1,l_{M-1}-1} $ $ j_{M-1,l_{M-1}-1} $ Then, let $ T $ be the number of operations, and output the operation sequence in the following format. > $ T $ $ m_0 $ $ d_0 $ $ \vdots $ $ m_{T-1} $ $ d_{T-1} $ In the $ t $ -th operation, the $ m_t $ -th conveyor belt is circularly shifted by one cell in direction $ d_t $ . The output must satisfy the following conditions. - $ 0\leq M\leq N^2 $ - The length $ l_m $ of each conveyor belt satisfies $ l_m\geq 2 $ . - Each coordinate $ (i_{m,x},j_{m,x}) $ satisfies $ 0\leq i_{m,x},j_{m,x}

### Scoring Let $ T $ be the length of the output operation sequence, and let $ B $ be the number of boxes successfully moved out. Then, you will obtain the following score. - If $ B=N^2 $ , $ 10^6 + \mathrm{round}\left(10^6 \log_2 \frac{10^5}{T}\right) $ - If $ B