AT_ahc070_a [AHC070A] Ward the Village

You are the chief of a village deep in the mountains of Japan, and the hauntings that break out every year during the Obon season have long troubled you. This year, a divination by the shrine maiden has revealed that $ 10000 $ hauntings will occur throughout the village. You therefore decided to set up protective talismans as close as possible to where the hauntings occur, so as to limit the damage. The divination tells you where the hauntings occur and in what order, but it grants you no time to prepare. You must leave the shrine on the outskirts of the village and travel around, setting up talismans while the hauntings are already taking place. A talisman wards off the hauntings with the divine power it inherits from the shrine or the talisman set up immediately before it. The shrine maiden's prayer can open at most $ 3 $ paths for the divine power, and you choose the positional relationships they run along before you leave the shrine. Please keep the damage to the village as small as you can.

The village is divided into an $ N\times N $ grid of cells. 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 coordinates $ (a_t,b_t) $ of the cell where a haunting occurs on each turn $ t=0,1,\cdots,N^2-1 $ are given as input in advance. First, you freely choose $ M $ positional relationships $ (i_0,j_0),\cdots,(i_{M-1},j_{M-1}) $ along which the divine power may run. Here, for every $ m $ with $ 0\leq m

Input is given from Standard Input in the following format. > $ N $ $ M $ $ a_0 $ $ b_0 $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N^2-1} $ $ b_{N^2-1} $ Each value satisfies the following constraints. - $ N=100 $ - $ M=3 $ - $ 0\leq a_t

Output to Standard Output in the following format. > $ i_0 $ $ j_0 $ $ i_1 $ $ j_1 $ $ \vdots $ $ i_{M-1} $ $ j_{M-1} $ $ m_0 $ $ m_1 $ $ \vdots $ $ m_{N^2-1} $ [Show example](https://img.atcoder.jp/ahc070/f4sYgUzY.html?lang=en&seed=0&output=sample)

### Scoring Let $ D $ be the danger level after all $ N^2 $ turns have finished. You then obtain the following score. \\\[ \\mathrm{round}\\left(\\frac{10^6\\times N^3}{D+1}\\right) \\\] There are 150 test cases, and the score of a submission is the sum of the scores for all test cases. 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 $ N=100 $ and $ M=3 $ are fixed. $ (a_0,b_0),\cdots,(a_{N^2-1},b_{N^2-1}) $ is a uniformly random permutation of the coordinates of all $ N^2 $ cells of the grid. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc070/f4sYgUzY.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc070/f4sYgUzY.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). If it does not compile, please try `rustup update`. - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc070/f4sYgUzY_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. **Starting with this short contest, the use of generative AI will be prohibited, with limited exceptions. Please refer to [this post](https://atcoder.jp/posts/short-ahc-llm-rules-en) for further details.**