#P17708. [2026年江苏省队集训]心灵感应

[2026年江苏省队集训]心灵感应

题面描述

你买下了一块 n×nn\times n 的绿地,这块绿地可以被表示为二维平面上 [1,n]×[1,n][1,n]\times[1,n] 的矩形。

你现在在 (1,1)(1,1),你需要前往 (n,n)(n,n) 执行必要的工作。你不喜欢绕远路,因此你的每一步行动都必须向右或向上,即从 (x,y)(x,y) 移动到 (x+1,y)(x+1,y) 或 (x,y+1)(x,y+1)。

为了抵御吞噬世界的黑暗,你的绿地上有一些光灵草。具体地,所有在 [xl,xr]×[yl,yr][xl,xr]\times[yl,yr] 矩形内的整点位置都生有一棵光灵草。

光灵草是喜欢亲近的生物,你每到一个整点 (x,y)(x,y),一个处于 (a,b)(a,b) 位置的光灵草就会积攒 ∣x−a∣+∣y−b∣|x-a|+|y-b| 的焦躁值 (你可以走到存在光灵草的整点)。

有一个常数 TT。在你到达 (n,n)(n,n) 之后,如果有任意一棵光灵草的焦躁值 >T>T,那么光灵草就会感觉自己被冷落并变得黯淡,你想避免这种情况的发生。

你的路径可以被表示为一个长为 2n−22n-2 的由 R 和 U 组成的字符串,表示你每一步是向右还是向上。为了避免世界线的变动,你想求出多种方案。具体地,给定常数 mm,设总共有 cc 种合法的方案,你需要输出字典序前 min⁡(m,c)\min(m,c) 小的方案。

输入格式

第一行三个整数 n,m,Tn,m,T,表示绿地的大小,需要输出的方案数量,以及题面中的常数。

第二行四个整数 xl,yl,xr,yrxl,yl,xr,yr,表示光灵草的矩形范围。请注意四个变量输入的顺序。

输出格式

设一共有 cc 种合法的方案。

请输出 min⁡(m,c)\min(m,c) 行,每行一个长为 2n−22n-2 的字符串由 R 和 U 组成的字符串,第 ii 行表示字典序第 ii 小的合法方案。

输入输出样例

输入样例 #1

6 10 35
2 4 5 5

输出样例 #1

RRUUURURRU
RRUUURURUR
RRUUURUURR
RRUUUURRRU
RRUUUURRUR
RRUUUURURR
RRUUUUURRR
RURURUURRU
RURURUURUR
RURURUUURR

输入输出样例 2~6

请在下发文件中查看。

数据范围

对于所有数据,2≤n≤1062\le n\le10^6, m≥1m\ge1, nm≤2×106nm\le2\times10^6, 0≤T≤10180\le T\le10^{18}, 1≤xl≤xr≤n1\le xl\le xr\le n, 1≤yl≤yr≤n1\le yl\le yr\le n.

特殊限制如下,留空表示无特殊限制。

子任务编号 n,mn,m 特殊限制 子任务分值
1 n≤12n\le12 1313
2 n≤1000,nm≤3000n\le1000,nm\le3000 xl=xr,yl=yrxl=xr,yl=yr 1818
3 m=1m=1 1212
4 1616
5 xl=xr,yl=yrxl=xr,yl=yr
6 m=1m=1 1010
7 1515