#P17970. Following Arrows

Following Arrows

Following Arrows

题目描述

Panda 想设计一个由箭头组成的迷宫。迷宫是一个 NN 行、MM 列的网格,每个格子中有一个箭头:L、R、U、D 分别表示左、右、上、下。

格子用 (x,y)(x,y) 表示,其中 1≤x≤N1\le x\le N,1≤y≤M1\le y\le M。玩家从左上角 (1,1)(1,1) 出发,在第一次到达右下角 (N,M)(N,M) 时停止。每一步依次进行以下操作:

  1. 按当前位置的箭头移动一格。如果这次移动会越出网格,则留在原地。
  2. 将移动前所在格子中的箭头反转:L 与 R 互换,U 与 D 互换。即使因为越界而没有移动,也要反转当前位置的箭头。

给定 kk,请构造一个大小不超过 8×88\times8 的迷宫,使玩家恰好经过 kk 步第一次到达终点,或判断不存在这样的迷宫。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例一行,一个整数 kk。

输出格式

对于每个测试用例,如果不存在合法迷宫,输出一行 -1 -1。

否则,先输出一行两个整数 N,MN,M,再输出 NN 行,每行一个长度为 MM 的字符串,描述这一行的箭头。字符串只能包含 L、R、U、D。

如果有多种合法答案,输出任意一种。

数据范围

  • 1≤T≤2×1041\le T\le 2\times10^4;
  • 1≤k≤1061\le k\le10^6;
  • 所有测试用例的 kk 之和不超过 8×1078\times10^7;
  • 输出的迷宫必须满足 1≤N,M≤81\le N,M\le8。

样例

输入

5
1
4
9
16
25

输出

1 2
RR
2 2
LU
RD
3 2
LU
DR
LL
3 2
LU
UR
LL
1 6
LLRLLR