题意
- 给定一些点，要求构造一个操作序列一直循环，使得在特定时间经过那些点
考虑转换坐标系将((x, y))变成((x + y, x - y))，这样向上下左右移动的操作就变成了((+1, -1), (-1, +1), (-1, -1), (+1, +1))，这样就能让(x)坐标与(y)坐标独立开来
于是问题转化为，求一个序列里面只有(-1)或(1)，要让某个前缀加上一些总和等于某个给定的值，即:
令(S)为前缀和
[A_i S_n + S_i = B_i\
S_i = -A_i S_n + B_i
]
所以我们只需要差分一下，让相邻的两个(S)相差的绝对值小于等于位置之差就行：
[|S_i - S_j| leq |i - j|
]
这样就可以解出(S_n)的一个范围，我们任取一个就行
对于相邻的两个(S)我们只需要构造一个序列，使得中间这一段加起来等于它们的差分，解个二元方程即可
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 2000000
using namespace std;
int n, m, a[2][maxn + 5], vis[maxn + 5];
LL t[maxn + 5], pos[2][maxn + 5];
int tt;
struct Node{LL a, b, c;} ord[maxn + 5];
template <class T>
void read(T &x){
char ch;
bool ok;
for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
if(ok) x = -x;
}
int L, R;
void get_rge(LL x, LL y, LL z){
if(!x) return;
LD l = (LD)(z - y) / x, r = (LD)(-z - y) / x;
if(l > r) swap(l, r);
L = max(L, (int)ceil(l - eps));
R = min(R, (int)floor(r + eps));
}
int fl = 1;
void sol(int ty){
memset(vis, 0, sizeof vis);
memset(ord, 0, sizeof ord);
For(i, 1, n){
LL a = -t[i] / m, to = t[i] % m;
if(to == m - 1){
if(vis[to]){if(pos[ty][i] / (-a + 1) != ord[to].b){fl = 0; return;}}
else{
vis[to] = 1;
ord[to].b = pos[ty][i] / (-a + 1);
}
continue;
}
if(vis[to]){
if(ord[to].a == a && ord[to].b != pos[ty][i]){fl = 0; return;}
if((pos[ty][i] - ord[to].b) % (ord[to].a - a)){fl = 0; return;}
LL tem = (pos[ty][i] - ord[to].b) / (ord[to].a - a);
if(vis[m - 1] && ord[m - 1].b != tem){fl = 0; return;}
vis[m - 1] = 1;
ord[m - 1] = (Node){0, tem};
}
else{
vis[to] = 1;
ord[to] = (Node){a, pos[ty][i]};
}
}
L = ord[m - 1].b; R = ord[m - 1].b;
if(!vis[m - 1]){
L = -inf; R = inf;
int pre = -1;
For(i, 1, m - 2) if(vis[i]){
get_rge(ord[i].a - ord[pre == -1 ? m : pre].a, ord[i].b - ord[pre == -1 ? m : pre].b, i - pre);
pre = i;
}
get_rge(1 - ord[pre == -1 ? m : pre].a, -ord[pre == -1 ? m : pre].b, m - 1 - pre);
if(L > R){fl = 0; return;}
ord[m - 1].b = L;
vis[m - 1] = 1;
}
ord[m - 1].c = ord[m - 1].b;
/*if(tt == 146){
cout << L << " " << R << endl;
cout << ord[0].a << " " << ord[0].b << endl;
cout << ord[2000].a << " " << ord[2000].b << endl;
cout << ord[4000].a << " " << ord[4000].b << endl;
cout << ord[6000].a << " " << ord[6000].b << endl;
}*/
LL tem = ord[m - 1].c, pre = -1;
For(i, 0, m - 1) if(vis[i]){
if(i != m - 1) ord[i].c = tem * ord[i].a + ord[i].b;
if((ord[i].c - ord[pre == -1 ? m : pre].c + i - pre) % 2) break;
LL tem1 = (ord[i].c - ord[pre == -1 ? m : pre].c + i - pre) / 2;
if(tem1 > i - pre){fl = 0; return;}
For(j, pre + 1, pre + tem1) a[ty][j] = 1;
pre = i;
if(i == m - 1) return;
}
if(tem + 1 >= L && tem + 1 <= R){
memset(a[ty], 0, sizeof a[ty]);
tem = ++ord[m - 1].c; pre = -1;
For(i, 0, m - 1) if(vis[i]){
if(i != m - 1) ord[i].c = tem * ord[i].a + ord[i].b;
if((ord[i].c - ord[pre == -1 ? m : pre].c + i - pre) % 2){fl = 0; return;}
LL tem1 = (ord[i].c - ord[pre == -1 ? m : pre].c + i - pre) / 2;
if(tem1 > i - pre){fl = 0; return;}
For(j, pre + 1, pre + tem1) a[ty][j] = 1;
pre = i;
}
}
else fl = 0;
}
int main(){
//freopen("in", "r", stdin);
read(n); read(m);
For(i, 1, n){
LL x, y; read(t[i]); read(x); read(y); t[i]--;
if(i == 2) tt = y;
LL tem = x;
x = x + y;
y = tem - y;
pos[0][i] = x;
pos[1][i] = y;
}
sol(1);
if(!fl){puts("NO"); return 0;}
sol(0);
if(!fl){puts("NO"); return 0;}
For(i, 0, m - 1){
if(!a[0][i] && !a[1][i]) putchar('L');
if(!a[0][i] && a[1][i]) putchar('D');
if(a[0][i] && !a[1][i]) putchar('U');
if(a[0][i] && a[1][i]) putchar('R');
}
return 0;
}