AT_ahc046_a [AHC046A] Skating with Blocks

There is a skating rink consisting of $ N \times N $ squares. Let $ (0, 0) $ be the coordinates of the top-left square, and $ (i, j) $ be the coordinates of the square located $ i $ squares down and $ j $ squares to the right from there. All squares outside the $ N \times N $ area are covered with blocks and are impassable. Initially, there are no blocks inside the $ N \times N $ area. You start at the initial position $ (i_0, j_0) $ and must visit the specified target squares $ (i_1, j_1), \dots, (i_{M-1}, j_{M-1}) $ in the given order. At each turn, you may choose one of the four cardinal directions and perform one of the following actions: - **Move**: Move one square in the specified direction. You cannot move into a square containing a block. - **Slide**: Continue sliding in the specified direction until you hit a block. - **Alter**: Place a block on the adjacent square in the specified direction if it does not already contain one; otherwise, remove the existing block. You may not specify a square outside the $ N \times N $ area. It is also allowed to place a block on a current or future target square; however, you must remove the block in order to visit that square. If you slide over a target square without stopping on it, it is **not** considered visited. A target square is considered visited only if you either stop on it after a **Slide**, or move onto it directly via a **Move**. You must visit the target squares in the given order. Even if you pass over a later target square before visiting earlier ones, it is not considered visited at that time. You will need to visit it again when its turn in the sequence arrives. You may perform at most $ 2NM $ actions. Visit all target squares in the specified order using as few turns as possible.

Input is given from Standard Input in the following format: > $ N $ $ M $ $ i_0 $ $ j_0 $ $ \vdots $ $ i_{M-1} $ $ j_{M-1} $ - In all test cases, $ N = 20 $ and $ M = 40 $ are fixed. - The coordinates $ (i_k, j_k) $ of the initial position and each target square are integers satisfying $ 0 \leq i_k, j_k \leq N-1 $ , and all coordinates are distinct.

At each turn, represent the selected action and direction using a single uppercase alphabet letter as follows. **Actions** - Move: `M` - Slide: `S` - Alter: `A` **Directions** - Up: `U` - Down: `D` - Left: `L` - Right: `R` Let $ a_t $ and $ d_t $ denote the action and direction selected at turn $ t $ ( $ t = 0, 1, \dots, T-1 $ ), respectively. Then, output to Standard Output in the following format: > $ a_0 $ $ d_0 $ $ \vdots $ $ a_{T-1} $ $ d_{T-1} $ [Show example](https://img.atcoder.jp/ahc046/EuNd3uow.html?lang=en&seed=0&output=sample)

### Scoring Let $ T $ be the length of the output action sequence, and $ m $ be the number of target squares successfully visited. Then, you will obtain the following score. - If $ m