English · Original
Chinese · Translation
Formal · Original
Fox Ciel safely returned to her castle, but there was something wrong with the security system of the castle: sensors attached in the castle were covering her.
Ciel is at point (1, 1) of the castle now, and wants to move to point (_n_, _n_), which is the position of her room. By one step, Ciel can move from point (_x_, _y_) to either (_x_ + 1, _y_) (rightward) or (_x_, _y_ + 1) (upward).
In her castle, _c_2 sensors are set at points (_a_ + _i_, _b_ + _j_) (for every integer _i_ and _j_ such that: 0 ≤ _i_ < _c_, 0 ≤ _j_ < _c_).
Each sensor has a count value and decreases its count value every time Ciel moves. Initially, the count value of each sensor is _t_. Every time Ciel moves to point (_x_, _y_), the count value of a sensor at point (_u_, _v_) decreases by (|_u_ - _x_| + |_v_ - _y_|). When the count value of some sensor becomes **strictly less than** 0, the sensor will catch Ciel as a suspicious individual!
Determine whether Ciel can move from (1, 1) to (_n_, _n_) without being caught by a sensor, and if it is possible, output her steps. Assume that Ciel can move to every point even if there is a censor on the point.
## Input
In the first line there are five integers _n_, _t_, _a_, _b_, _c_ (2 ≤ _n_ ≤ 2·105, 0 ≤ _t_ ≤ 1014, 1 ≤ _a_ ≤ _n_ - _c_ + 1, 1 ≤ _b_ ≤ _n_ - _c_ + 1, 1 ≤ _c_ ≤ _n_).
Please do not use the _%lld_ specificator to read or write 64-bit integers in C++. It is preferred to use the _cin_ stream (also you may use the _%I64d_ specificator).
## Output
If Ciel's objective is possible, output in first line 2_n_ - 2 characters that represent her feasible steps, where _i_\-th character is _R_ if _i_\-th step is moving rightward, or _U_ if moving upward. If there are several solution, output **lexicographically first** one. Character _R_ is lexicographically earlier than the character _U_.
If her objective is impossible, output _Impossible_.
[samples]
## Note
The answers for the first sample and the second sample are shown on the picture:
<center></center>Here, a red point represents a point that contains a sensor.
Fox Ciel 安全返回了她的城堡，但城堡的安全系统出了问题：安装在城堡中的传感器正在监视她。
Ciel 目前位于城堡的点 #cf_span[(1, 1)]，她希望移动到点 #cf_span[(n, n)]，即她的房间所在位置。每一步，Ciel 可以从点 #cf_span[(x, y)] 移动到 #cf_span[(x + 1, y)]（向右）或 #cf_span[(x, y + 1)]（向上）。
在她的城堡中，#cf_span[c2] 个传感器被设置在点 #cf_span[(a + i, b + j)]（对所有满足 #cf_span[0 ≤ i < c, 0 ≤ j < c] 的整数 #cf_span[i] 和 #cf_span[j]）。
每个传感器有一个计数值，每当 Ciel 移动时，该值会减少。初始时，每个传感器的计数值为 #cf_span[t]。每当 Ciel 移动到点 #cf_span[(x, y)] 时，位于点 #cf_span[(u, v)] 的传感器的计数值会减少 #cf_span[|u - x| + |v - y|]。当某个传感器的计数值变得 *严格小于* #cf_span[0] 时，该传感器会将 Ciel 识别为可疑人员并捕获她！
请判断 Ciel 是否能从 #cf_span[(1, 1)] 移动到 #cf_span[(n, n)] 而不被任何传感器捕获；如果可能，请输出她的移动路径。假设 Ciel 可以移动到任何点，即使该点上有传感器。
第一行包含五个整数 #cf_span[n, t, a, b, c]（#cf_span[2 ≤ n ≤ 2·105, ] #cf_span[0 ≤ t ≤ 1014, ] #cf_span[1 ≤ a ≤ n - c + 1, ] #cf_span[1 ≤ b ≤ n - c + 1, ] #cf_span[1 ≤ c ≤ n]）。
在 C++ 中，请勿使用 _%lld_ 格式说明符读取或写入 64 位整数。建议使用 _cin_ 流（也可以使用 _%I64d_ 格式说明符）。
如果 Ciel 的目标可以达成，请在第一行输出 #cf_span[2n - 2] 个字符，表示她的可行路径，其中第 #cf_span[i] 个字符为 _R_ 表示第 #cf_span[i] 步是向右移动，为 _U_ 表示向上移动。如果有多个解，请输出字典序最小的一个。字符 _R_ 在字典序上早于 _U_。
如果目标无法达成，请输出 _Impossible_。
第一组样例和第二组样例的答案如图所示：
## Input
第一行包含五个整数 #cf_span[n, t, a, b, c]（#cf_span[2 ≤ n ≤ 2·105, ] #cf_span[0 ≤ t ≤ 1014, ] #cf_span[1 ≤ a ≤ n - c + 1, ] #cf_span[1 ≤ b ≤ n - c + 1, ] #cf_span[1 ≤ c ≤ n]）。在 C++ 中，请勿使用 _%lld_ 格式说明符读取或写入 64 位整数。建议使用 _cin_ 流（也可以使用 _%I64d_ 格式说明符）。
## Output
如果 Ciel 的目标可以达成，请在第一行输出 #cf_span[2n - 2] 个字符，表示她的可行路径，其中第 #cf_span[i] 个字符为 _R_ 表示第 #cf_span[i] 步是向右移动，为 _U_ 表示向上移动。如果有多个解，请输出字典序最小的一个。字符 _R_ 在字典序上早于 _U_。如果目标无法达成，请输出 _Impossible_。
[samples]
## Note
第一组样例和第二组样例的答案如图所示： 其中，红色点表示包含传感器的点。
**Definitions**
Let $ n, t, a, b, c \in \mathbb{Z} $ be given parameters.
Let $ S = \{ (u, v) \mid u \in [a, a+c-1],\ v \in [b, b+c-1] \} $ be the set of sensor positions (a $ c \times c $ grid).
Each sensor at $ (u, v) \in S $ has an initial count value $ t $.
Ciel starts at $ (1, 1) $ and must reach $ (n, n) $, moving only right ($ R $: $ (x,y) \to (x+1,y) $) or up ($ U $: $ (x,y) \to (x,y+1) $).
A path is a sequence of $ 2n - 2 $ moves: $ p = (m_1, m_2, \dots, m_{2n-2}) $, where each $ m_i \in \{R, U\} $.
Let $ (x_k, y_k) $ denote Ciel’s position after $ k $ moves, with $ (x_0, y_0) = (1,1) $, and $ (x_{2n-2}, y_{2n-2}) = (n,n) $.
For each sensor $ (u, v) \in S $, the total decrease in its count value along path $ p $ is:
$$
D(u,v) = \sum_{k=0}^{2n-2} \left( |u - x_k| + |v - y_k| \right)
$$
The sensor at $ (u,v) $ triggers if $ D(u,v) > t $ (i.e., if the count becomes strictly less than 0).
**Constraints**
1. $ 2 \le n \le 2 \cdot 10^5 $
2. $ 0 \le t \le 10^{14} $
3. $ 1 \le a \le n - c + 1 $, $ 1 \le b \le n - c + 1 $, $ 1 \le c \le n $
4. All positions $ (x_k, y_k) $ lie in $ [1, n] \times [1, n] $
**Objective**
Determine whether there exists a path from $ (1,1) $ to $ (n,n) $ such that for all $ (u,v) \in S $:
$$
\sum_{k=0}^{2n-2} \left( |u - x_k| + |v - y_k| \right) \le t
$$
If such a path exists, output the lexicographically smallest sequence of $ R $ and $ U $ moves (i.e., prioritize $ R $ over $ U $ at each choice).
Otherwise, output `Impossible`.
API Response (JSON)
{
"problem": {
"name": "E. Security System",
"description": {
"content": "Fox Ciel safely returned to her castle, but there was something wrong with the security system of the castle: sensors attached in the castle were covering her. Ciel is at point (1, 1) of the castle n",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF79E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Fox Ciel safely returned to her castle, but there was something wrong with the security system of the castle: sensors attached in the castle were covering her.\n\nCiel is at point (1, 1) of the castle n...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Fox Ciel 安全返回了她的城堡，但城堡的安全系统出了问题：安装在城堡中的传感器正在监视她。\n\nCiel 目前位于城堡的点 #cf_span[(1, 1)]，她希望移动到点 #cf_span[(n, n)]，即她的房间所在位置。每一步，Ciel 可以从点 #cf_span[(x, y)] 移动到 #cf_span[(x + 1, y)]（向右）或 #cf_span[(x, y + 1)]（向上...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, t, a, b, c \\in \\mathbb{Z} $ be given parameters. \nLet $ S = \\{ (u, v) \\mid u \\in [a, a+c-1],\\ v \\in [b, b+c-1] \\} $ be the set of sensor positions (a $ c \\times c $ grid). ...",
"is_translate": false,
"language": "Formal"
}
]
}