AT_ahc_genai_test_2026_a Dice Delivery

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. Each cell can hold at most one package. There are $ M $ packages, numbered $ 1,2,\ldots,M $ , with one package of each number. You are given their initial positions and their destination cells. The destinations are all distinct. You want to roll a die to carry these packages to their destinations. Each of the six faces of the die can hold at most one package. Initially, the die is at cell $ (0,0) $ , and all six faces are empty. In one operation, choose one of the four directions (up, down, left, or right) and perform the following two steps in order. 1. Roll the die 90 degrees in the chosen direction to the adjacent cell. 2. **Swap the package on the face now touching the grid with the package in the cell it has moved to.** If only one of the two holds a package, move that package to the other; if both are empty, nothing happens. You cannot roll without swapping, or swap without rolling. You cannot roll outside the grid. No swap between cell $ (0,0) $ and the bottom face takes place in the initial state. #### Rolling directions and faces Call the current faces the top face $ T $ , bottom face $ B $ , north face $ N $ , south face $ S $ , west face $ W $ , and east face $ E $ . North is the direction of decreasing row indices, and east is the direction of increasing column indices. The table below shows which face **before** a roll becomes each face **after** the roll. A package held by a face moves with that face. The swap described above then takes place. Operation Next cell New top New bottom New north New south New west New east `U` $ (i-1,j) $ $ S $ $ N $ $ T $ $ B $ $ W $ $ E $ `D` $ (i+1,j) $ $ N $ $ S $ $ B $ $ T $ $ W $ $ E $ `L` $ (i,j-1) $ $ E $ $ W $ $ N $ $ S $ $ T $ $ B $ `R` $ (i,j+1) $ $ W $ $ E $ $ N $ $ S $ $ B $ $ T $ You may perform at most $ 10000 $ operations. Carry as many packages as possible to their destinations using as few operations as possible. The final position and orientation of the die are unrestricted. The following example shows part of the grid. The operations `R`, `D`, `R`, `U`, `L` carry package $ 1 $ from $ (0,1) $ to $ (0,2) $ and package $ 2 $ from $ (1,1) $ to $ (0,1) $ . Packages $ 1 $ and $ 2 $ are placed at their destinations on the fourth and fifth operations, respectively. Five operations that deliver two packages

Input is given from Standard Input in the following format. > $ N $ $ M $ $ a_{0,0} $ $ \cdots $ $ a_{0,N-1} $ $ \vdots $ $ a_{N-1,0} $ $ \cdots $ $ a_{N-1,N-1} $ $ b_{0,0} $ $ \cdots $ $ b_{0,N-1} $ $ \vdots $ $ b_{N-1,0} $ $ \cdots $ $ b_{N-1,N-1} $ - $ N=16 $ and $ 51\le M\le166 $ . - $ a_{i,j} $ is the number of the package initially in cell $ (i,j) $ . 0 denotes an empty cell. - If $ b_{i,j}>0 $ , cell $ (i,j) $ is the destination of the package with that number. A cell with $ b_{i,j}=0 $ is not a destination. - Each of $ a $ and $ b $ contains every number $ 1,2,\ldots,M $ exactly once. All other entries are 0. - $ a_{0,0}=b_{0,0}=0 $ .

Output to Standard Output in the following format. Output $ T $ lines, where $ d_t $ is one of `U`, `D`, `L`, or `R`, indicating the direction of the $ t $ -th operation. > $ d_0 $ $ \vdots $ $ d_{T-1} $ [Show example](https://img.atcoder.jp/ahc_genai_test_2026/UkOQH5WY.html?lang=en&seed=0&output=sample)

### Scoring Let $ T $ be the number of operations in your output, and let $ E $ be the number of packages that are not in their destination cells after all operations. Your absolute score is \\\[ 1+T+10000E \\\] **The lower the absolute score, the better.** For each test case, you will obtain a **rank score** according to your rank determined by lower absolute score. The score of the submission is the total rank score for each test case. The rank score is calculated as follows, and the higher the rank score, the better. Let $ n_{submit} $ be the number of contestants with submissions, $ n_{lose} $ be the number of contestants who received an absolute score lower than yours, and $ n_{tie} $ be the number of other contestants who received an absolute score equal to yours. Then your rank in this test case is determined as $ r=n_{lose}+0.5 n_{tie} $ , and your rank score is $ \mathrm{round}(10^9\times (1-\frac{r}{n_{submit}})) $ . There are 100 test cases. There will be no system test after the contest; the standings once all submissions made during the contest have been judged are the final ranking. If your submission produces illegal output or exceeds the time limit for some test cases, only the rank score for those test cases will be zero. #### About relative evaluation system The standings will be calculated using only the last submission which received a result other than CE . The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the rank scores for the test cases that were answered correctly. ### Input Generation Let $ \operatorname{uniform}(L,U) $ denote a real number drawn uniformly at random from $ [L,U) $ . #### Parameters \\\[ \\rho=\\operatorname{uniform}(0.20,0.65),\\qquad \\sigma=\\exp(\\operatorname{uniform}(0,\\ln16)). \\\] Set $ N=16 $ and $ M=\mathrm{round}(\rho(N^2-1)) $ . $ \rho $ controls the package density, and $ \sigma $ controls the spread of distances between initial positions and destinations. These values are not included in the input. #### Initial positions Uniformly shuffle the $ N^2-1 $ cells other than $ (0,0) $ . Let $ s_1,\ldots,s_M $ be the first $ M $ cells in this order, and place package $ k $ in cell $ s_k $ . #### Destinations Uniformly shuffle the package numbers $ 1,\ldots,M $ , and process them in this order as follows. Initially, all cells other than $ (0,0) $ are unused as destinations. Let $ s_k=(r_k,c_k) $ be the initial position of package $ k $ . For each cell $ q=(r,c) $ that is unused as a destination, calculate the weight \\\[ w\_k(q)=\\exp\\left(-\\frac{(r-r\_k)^2+(c-c\_k)^2}{2\\sigma^2}\\right) \\\] Choose one of the unused cells with probability proportional to $ w_k(q) $ as the destination of package $ k $ . Remove the chosen cell from the set of unused cells. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc_genai_test_2026/UkOQH5WY.html?lang=en): This is more powerful than the local version providing animations and manual play. - [Local version](https://img.atcoder.jp/ahc_genai_test_2026/UkOQH5WY.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/ahc_genai_test_2026/UkOQH5WY_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.