Story

AtCoder is developing a route navigation application that utilizes shortest path algorithms. The service area is represented as a road network of 30x30 vertices connected in a grid. When a user specifies the vertex of the current location and the vertex of the destination, the app will output the shortest path between them. The trouble is that, even though the scheduled release date is approaching, the measurement of the length of each edge, which is essential for shortest path computations, is not finished at all. Therefore, AtCoder decided to give up measuring the edge length in advance and allows the app to output paths that are not the shortest. It should be possible to gradually improve the performance by estimating the length of each edge based on the information about the actual time users take to arrive at their destinations.

Problem Statement

There is an undirected grid graph with 30x30 vertices with unknown edge lengths. Let $(0, 0)$ denote the top-left vertex, and $(i, j)$ denote the vertex at the $i$-th row from the top and $j$-th column from the left. Your task is to process the following query 1000 times.

In the $k$-th query, your program first receives the vertices $s_k=(si_k,sj_k)$ and $t_k=(ti_k,tj_k)$ from Standard Input in the following format:

$si_k$ $sj_k$ $ti_k$ $tj_k$

Then, your program should compute a path $P_k$ from $s_k$ to $t_k$. Let U, D, L, and R represent the movement from $(i,j)$ to $(i-1,j)$, $(i+1,j)$, $(i,j-1)$, and $(i,j+1)$, respectively. Output a string representing the path $P_k$ to Standard Output in one line. After the output, you have to flush Standard Output. Otherwise, the submission might be judged as TLE.

After your program outputs a path, the judge program calculates the length $b_k$ of the path, generates a uniform random number $e_k$ between $0.9$ and $1.1$, and gives an integer value $\mathrm{round}(b_k\times e_k)$ to Standard Input. By reading that integer, the $k$-th query completes, and you should proceed to the $k+1$-th query.

Examples

3 19 16 17

DDDDDDDDDDDDDLL

99561

26 18 13 18

UUUUUUUUUUUUU

72947

Scoring

Let $a_k$ and $b_k$ be the lengths of the shortest path and the output path for the $k$-th query ($1\leq k\leq 1000$), respectively. Then the score for the test case is

$\mathrm{round}(2312311\times \sum_{k=1}^{1000}0.998^{1000-k} \frac{a_k}{b_k})$

The score of a submission is the total score for each test case. If your program outputs an illegal path (visiting the same vertex multiple times, going outside of 30x30, or not a path from $s$ to $t$), it is judged as WA. After the contest is over, the final ranking will be determined by system tests against the last submission.

• Provisional tests consist of 100 test cases. If you get a result other than AC for one or more test cases, the score of the submission will be zero.
• System tests consist of 3000 test cases. If you get a result other than AC for some test cases, only the score for those test cases will be zero. We will publish seeds.txt (md5=0cf5051d586e7f62c0b3527f6f7fbb1c) after the contest is over.

Input Generation

Let $\mathrm{rand}(L,U)$ be a function that generates a uniformly random integer between $L$ and $U$, inclusive. We first generate two parameters $D=\mathrm{rand}(100, 2000)$ and $M=\mathrm{rand}(1, 2)$. Let $h_{i,j}$ be the length of the edge between $(i, j)$ and $(i,j+1)$, and let $v_{i,j}$ be the length of the edge between $(i, j)$ and $(i+1,j)$.

Generation of $h_{i,j}$

1. For each $i\in\{0,\ldots,29\}$ and $p\in\{0,\ldots,M-1\}$, we independently generate a random integer $H_{i,p}=\mathrm{rand}(1000+D,9000-D)$.
2. For each $i\in\{0,\ldots,29\}$ and $j\in\{0,\ldots,28\}$, we independently generate a random integer $\delta_{i,j}=\mathrm{rand}(-D,D)$.
3. If $M=1$, for each $i\in\{0,\ldots,29\}$ and $j\in\{0,\ldots,28\}$, we set $h_{i,j}=H_{i,0}+\delta_{i,j}$.
4. If $M=2$, for each $i\in\{0,\ldots,29\}$, we generate a random integer $x_i=\mathrm{rand}(1,28)$, and then for each $j\in\{0,\ldots,x_i-1\}$, we set $h_{i,j}=H_{i,0}+\delta_{i,j}$, and for each $j\in\{x_i,\ldots,28\}$, we set $h_{i,j}=H_{i,1}+\delta_{i,j}$.

Generation of $v_{i,j}$

1. For each $j\in\{0,\ldots,29\}$ and $p\in\{0,\ldots,M-1\}$, we independently generate a random integer $V_{j,p}=\mathrm{rand}(1000+D,9000-D)$.
2. For each $i\in\{0,\ldots,28\}$ and $j\in\{0,\ldots,29\}$, we independently generate a random integer $\gamma_{i,j}=\mathrm{rand}(-D,D)$.
3. If $M=1$, for each $j\in\{0,\ldots,29\}$ and $i\in\{0,\ldots,28\}$, we set $v_{i,j}=V_{j,0}+\gamma_{i,j}$.
4. If $M=2$, for each $j\in\{0,\ldots,29\}$, we generate a random integer $y_j=\mathrm{rand}(1,28)$, and then for each $i\in\{0,\ldots,y_j-1\}$, we set $v_{i,j}=V_{j,0}+\gamma_{i,j}$, and for each $i\in\{y_j,\ldots,28\}$, we set $v_{i,j}=V_{j,1}+\gamma_{i,j}$.

Generation of $s_k$, $t_k$

The vertices $s_k$ and $t_k$ given in the query are chosen uniformly at random among all the vertices. If the Manhattan distance between $s_k$ and $t_k$ ($|si_k-ti_k|+|sj_k-tj_k|$) is strictly less than 10, we repeat the random selection until the distance becomes at least 10.

Tools

• Local tester: You need a compilation environment of Rust language.
• Visualizer
• Inputs: If you don't use the above local tester, you can instead use these 100 inputs (seed 0-99) for local testing. These inputs are different from the actual test cases. The inputs are in the following format, and you can use them by writing a judge program by yourself.

$h_{0,0}$ $\ldots$ $h_{0,28}$
$\vdots$
$h_{29,0}$ $\ldots$ $h_{29,28}$
$v_{0,0}$ $\ldots$ $v_{0,29}$
$\vdots$
$v_{28,0}$ $\ldots$ $v_{28,29}$
$si_1$ $sj_1$ $ti_1$ $tj_1$ $a_1$ $e_1$
$\vdots$
$si_{1000}$ $sj_{1000}$ $ti_{1000}$ $tj_{1000}$ $a_{1000}$ $e_{1000}$

Example of judge program (pseudo code)

string query(s, t, prev_result) {
    // WRITE YOUR SOLUTION HERE
}

int main() {
    if (LOCAL_TEST) {
        read_h_v();
    }
    prev_result = 0;
    score = 0.0;
    for (int k = 0; k < 1000; k++) {
        if (LOCAL_TEST) {
            read_s_t_a_e();
        } else {
            read_s_t();
        }
        path = query(s, t, prev_result);
        print(path);
        if (LOCAL_TEST) {
            b = compute_path_length(path);
            score = score * 0.998 + a / b;
            prev_result = round(b * e);
        } else {
            prev_result = read_result();
        }
    }
    if (LOCAL_TEST) {
        print(round(2312311 * score));
    }
    return 0;
}