Human Exercise

AtCoder

IDagc072_c

Time2000ms

Memory256MB

Difficulty—

AtCoder City is represented by an $N \times N$ grid. Let $(i, j)$ denote the cell at the $i$‑th row from the top $(1 \le i \le N)$ and the $j$‑th column from the left $(1 \le j \le N)$. Aoki performed the following **exercise** $K$ times for marathon training. 1. Start from cell $(1, 1)$. 2. Repeat the following action $2N-2$ times to reach cell $(N, N)$: * Move one cell down or right. If both moves are possible, choose the one whose destination cell has been visited fewer times in the previous exercises. If the counts are equal, choose the downward move. Print the path taken in the $K$‑th exercise. ## Constraints * $2 \le N \le 100$ * $1 \le K \le 10^{18}$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $K$ [samples]

Samples

Input #1

5 4

Output #1

RRDDRRDD

The 1st, 2nd, 3rd, and 4th exercises go as follows, so the answer is `RRDDRRDD`.
![image](https://img.atcoder.jp/agc072/bf631afab80dc49bc5ffd8d3ac085b08.png)

Input #2

10 869120

Output #2

RDRRRDRDRDRDRDDDRD

API Response (JSON)

{
  "problem": {
    "name": "Human Exercise",
    "description": {
      "content": "AtCoder City is represented by an $N \\times N$ grid. Let $(i, j)$ denote the cell at the $i$‑th row from the top $(1 \\le i \\le N)$ and the $j$‑th column from the left $(1 \\le j \\le N)$. Aoki performed",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc072_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "AtCoder City is represented by an $N \\times N$ grid. Let $(i, j)$ denote the cell at the $i$‑th row from the top $(1 \\le i \\le N)$ and the $j$‑th column from the left $(1 \\le j \\le N)$.\nAoki performed...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments