AT_ahc066_a [AHC066A] Macro Controller

CEO Takahashi of AtCoder Inc. likes ball games. However, while playing with various balls during breaks from work, he scattered balls all over the office. Seeing this, Vice President Aoki became very angry and ordered Takahashi to clean them up immediately. At a loss, Takahashi decided to use the cleaning robot he had recently purchased to put away the balls. This robot can move around the office and pick up or put down balls using the basic operations of moving forward, turning right, turning left, and swapping. Furthermore, the included controller has a macro function, which can record a sequence of operations and play it back later. Instead of Takahashi, put all the balls into their corresponding baskets using as short a sequence of operations as possible.

There is an $ N\times N $ grid. Let the coordinates of the top-left cell be $ (0,0) $ , and let the coordinates of the cell $ i $ cells downward and $ j $ cells to the right be $ (i,j) $ . The outer boundary of the grid is surrounded by walls, and there may also be walls between adjacent cells. It is guaranteed that every cell is reachable from every other cell by repeatedly moving up, down, left, and right without crossing walls. On the grid, there are $ M $ types of balls and $ M $ types of baskets. For each type $ k\ (0\leq k

Input is given from Standard Input in the following format. > $ N $ $ M $ $ T $ $ v_0 $ $ \vdots $ $ v_{N-1} $ $ h_0 $ $ \vdots $ $ h_{N-2} $ $ b_0 $ $ c_0 $ $ d_0 $ $ e_0 $ $ \vdots $ $ b_{M-1} $ $ c_{M-1} $ $ d_{M-1} $ $ e_{M-1} $ Here, $ (b_k,c_k) $ represents the initial position of the ball of type $ k $ , and $ (d_k,e_k) $ represents the position of the basket of type $ k $ . Each value satisfies the following constraints. - $ 10\leq N\leq 20 $ - $ N/2\leq M\leq 2N $ - $ 1\leq T\leq 2N^2 M $ - $ v_{i,0} \cdots v_{i,N-2} $ is a string of length $ N-1 $ consisting of `0` and `1`; its $ j $ -th character $ v_{i,j} $ indicates whether there is (`1`) or is not (`0`) a wall between cell $ (i, j) $ and cell $ (i, j+1) $ . - $ h_{i,0} \cdots h_{i,N-1} $ is a string of length $ N $ consisting of `0` and `1`; its $ j $ -th character $ h_{i,j} $ indicates whether there is (`1`) or is not (`0`) a wall between cell $ (i, j) $ and cell $ (i+1, j) $ . - It is guaranteed that every cell is reachable from every other cell. - All initial positions of balls and positions of baskets are distinct.

Let $ A $ be the length of the operation sequence, and let $ a_t $ be the character (`F`, `R`, `L`, `S`, `M`, `P`) representing the $ t $ -th operation. Output to Standard Output in the following format. > $ a_0 $ $ \vdots $ $ a_{A-1} $ The length $ A $ of the output operation sequence must be at most $ T $ . [View an example](https://img.atcoder.jp/ahc066/O25rQjiK.html?lang=ja&seed=0&output=sample)

### Scoring Let $ A $ be the length of the output operation sequence. Here, `M` and `P` are each counted as one button operation. Let $ V $ be the number of balls placed on the cells of their corresponding baskets at the end of the simulation. For each test case, the following absolute score is obtained. - If $ V=M $ , $ A $ - If $ V