AT_ahc073_a [AHC073A] Circles of Inversion

Takahashi the wizard wants to visit several destinations in a specified order using "circles of inversion." By choosing a magic circle drawn in advance and making it react with a new circle drawn at his current position, he can instantly teleport to the point symmetric to his current position about the chosen circle. The circle used for teleportation disappears, but the new circle at his position before teleportation remains and can be used for another teleportation. Before setting out, Takahashi can draw several magic circles wherever he likes. Help him choose their positions and combine walking and teleportation to visit all the destinations in order with as few operations as possible. 

There is an $ N\times N $ grid. 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. Takahashi the wizard moves on this grid. You are given his initial position $ s=(s_i,s_j) $ and $ M $ destinations $ g_0,\ldots,g_{M-1} $ to visit in order. You first draw $ K $ magic circles in cells of your choice on the grid. Takahashi and magic circles, or multiple magic circles, may occupy the same cell and do not obstruct each other. Repeat the following operations. - Walk: Move Takahashi to an adjacent cell up, down, left, or right. The destination cell must be inside the grid. - Teleport: Choose a cell containing a magic circle, then draw a new magic circle at Takahashi's current position. Takahashi teleports to the point symmetric to his current position about the chosen cell. That is, if his position before the operation is $ (i,j) $ and the chosen cell is $ (a,b) $ , move him to $ (2a-i,2b-j) $ . Remove one magic circle from the chosen cell, leaving the new circle drawn at the departure point $ (i,j) $ . This operation is allowed only if the destination cell is inside the grid. All other magic circles remain unchanged. Let $ T $ be the minimum number of operations needed to visit all destinations in the specified order from the initial position using only walking. In other words, $ T $ is the sum of the Manhattan distance from the initial position to the first destination and the Manhattan distances between consecutive destinations. You may perform at most $ T $ operations in total. Immediately after each operation, if Takahashi is at the next destination, it is counted as visited. Arriving at any other destination does not increase the number of visited destinations. Even if he reaches a later destination early, he must visit it again when its turn comes. Choose the initial positions of the magic circles and a sequence of operations to visit all destinations in the specified order with as few operations as possible.

Input is given from Standard Input in the following format. > $ N $ $ M $ $ K $ $ T $ $ s_i $ $ s_j $ $ g_{0,i} $ $ g_{0,j} $ $ \vdots $ $ g_{M-1,i} $ $ g_{M-1,j} $ Here, $ g_r=(g_{r,i},g_{r,j}) $ is the $ r $ -th destination. Each value satisfies the following constraints. - $ N=128 $ - $ M=150 $ - $ K=3 $ - $ T $ is the minimum number of operations needed to visit all destinations using only walking, as defined above. - All coordinate components are integers between $ 0 $ and $ N-1 $ , inclusive. - $ s,g_0,\ldots,g_{M-1} $ are all distinct.

Output to Standard Output in the following format. > $ a_0 $ $ b_0 $ $ \vdots $ $ a_{K-1} $ $ b_{K-1} $ $ \mathrm{op}_0 $ $ \vdots $ $ \mathrm{op}_{A-1} $ In the first $ K $ lines, output the coordinates $ (a_k,b_k) $ of the $ K $ magic circles drawn in advance, in any order. Each coordinate component must be an integer between $ 0 $ and $ N-1 $ , inclusive. Then output one operation per line in the following format. - Walk up, down, left, or right: `U`, `D`, `L`, or `R`, respectively. - Teleport using a magic circle at $ (a,b) $ : `J` $ a $ $ b $ The coordinates specified for teleportation must satisfy $ 0\leq a,b

### Scoring Let $ A $ be the length of the output operation sequence and $ V $ be the number of destinations visited in the specified order. Your score is calculated as follows. \\\[ \\begin{cases} M+T-A+1 & (V=M) \\\\ V+1 & (V<M) \\end{cases} \\\] 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 Choose an ordered sequence of $ M+1 $ distinct cells uniformly at random from the $ N^2 $ cells, and use the first cell as $ s $ and the remaining cells as $ g_0,\ldots,g_{M-1} $ in order. Compute $ T $ from the chosen initial position and destinations. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc073/A21qfZSs.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc073/A21qfZSs.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/ahc073/A21qfZSs_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.