2026 National Invitational of CCPC (Qinhuangdao) and the 10th Hebei Collegiate Programming Contest
A. 求求你不要再摔馍片了
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Asrit 有 $$$n$$$ 包馍片，它们排成一排。馍片共有 $$$5$$$ 种不同的味道：香葱味、孜然味、烧烤味、麻辣味、牛肉味。为了方便，我们将味道分别记为 $$$1 \sim 5$$$，其中第 $$$i$$$ 包馍片的味道为 $$$a_i$$$。

每当 Asrit 吃一包馍片时，他会获得 $$$1$$$ 点开心度。但是，总是吃同一种味道的馍片会很乏味。具体来说，如果 Asrit 先吃了一包味道为 $$$x$$$ 的馍片，紧接着吃的下一包馍片味道为 $$$y$$$，则他会额外获得 $$$(y - x + 5) \bmod 5$$$ 点开心度。

为了吃得更美味，Asrit 决定调整吃馍片的顺序。他会按照初始顺序依次处理每一包馍片，对于当前处理的馍片，选择是否将其扔到序列的最后。注意，一包馍片不能被扔两次，不然它会碎掉。

处理完所有馍片后，Asrit 会按照新的顺序依次吃掉它们。请问 Asrit 可以获得的最大开心度是多少？

Input

第一行输入一个整数 $$$n$$$ $$$(1 \le n \le 10^5)$$$，表示馍片的数量。

第二行输入 $$$n$$$ 个整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 5)$$$，表示每包馍片的味道。

Output

输出一行一个整数，表示 Asrit 能获得的最大开心度。

Examples
Input
6
1 1 1 1 1 1
Output
6
Input
6
5 5 4 3 2 1
Output
26
Input
6
1 1 2 3 4 5
Output
15
Note

样例 $$$3$$$ 解释：将第 $$$1$$$ 包馍片和第 $$$6$$$ 包馍片扔到最后，最后吃的序列为 1 2 3 4 1 5，此时答案最大。

B. 一句祝贺
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

第十届河北省大学生程序设计竞赛，同时也是 2026 年中国大学生程序设计竞赛全国邀请赛（秦皇岛），在组织者的不懈努力下终于顺利举行。

从筹备到现场，每一个环节都充满挑战，但凭借所有参与者的共同付出，这场赛事得以呈现于大家面前。

作为参赛选手中的一员，你希望用一句话表达对这场赛事成功举办的祝贺。请输出下面指定的句子。

Input

无

Output

输出 "Congratulations on the success of the 10th Hebei CPC and the 2026 CCPC National Invitational (Qinhuangdao)!"（不含引号）

C. 世界树
time limit per test
10 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一棵 $$$n$$$ 个节点的无根树 $$$T$$$，节点编号为 $$$1$$$ 到 $$$n$$$，每条边有一个整数边权（可能为负）。

定义树上两点 $$$a,b$$$ 的距离 $$$\operatorname{dis}(a,b)$$$ 为它们之间的唯一简单路径上的边权之和。

现有 $$$q$$$ 次查询，每次查询给定两个节点 $$$x$$$ 和 $$$y$$$，请你计算并输出： $$$$$$ \max_{u \in T}\bigl(\operatorname{dis}(x,u)+\operatorname{dis}(y,u)\bigr) $$$$$$

Input

第一行两个整数 $$$n,q$$$ ($$$1\le n,q\le 5\times 10^5$$$)，分别表示树的节点数和查询次数。

接下来 $$$n-1$$$ 行，每行三个整数 $$$u,v,w$$$ ($$$1\le u,v\le n$$$, $$$|w|\le 10^9$$$)，表示节点 $$$u$$$ 与节点 $$$v$$$ 之间有一条边权为 $$$w$$$ 的边。保证输入构成一棵树。

接下来 $$$q$$$ 行，每行两个整数 $$$x,y$$$ ($$$1\le x,y\le n$$$)，表示一次查询。

Output

共 $$$q$$$ 行，对于每次查询，输出一行一个整数，表示所求的最大值。

Example
Input
4 3
1 2 1
2 3 2
2 4 -1
1 1
1 2
1 3
Output
6
5
3

D. 简单字符串题
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

我们可以定义 $$$AB$$$ 表示两个字符串 $$$A$$$，$$$B$$$ 相连接，例如 $$$A = \texttt{aab}$$$，$$$B = \texttt{ab}$$$，则 $$$AB = \texttt{aabab}$$$。

并递归地定义 $$$A^1=A$$$，$$$A^n = A^{n - 1} A$$$（$$$n \ge 2$$$ 且为正整数）。例如 $$$A = \texttt{abb}$$$，则 $$$A^3=\texttt{abbabbabb}$$$。

现给定一个长度为 $$$n$$$ 的字符串 $$$S$$$，给定常数 $$$k$$$，求 $$$S = A^iB_1B_2\dots B_kC^j$$$ 的方案数，其中 $$$A,B_1,B_2,\dots,B_k,C$$$ 为任意非空字符串，$$$i,j$$$ 为任意正整数。

两种方案不同当且仅当 $$$A$$$、$$$B_1$$$、$$$B_2$$$、$$$\dots$$$、$$$B_k$$$、$$$C$$$、$$$i$$$、$$$j$$$ 中有至少一个字符串或数字不同。

答案要对 $$$998244353$$$ 取模。

Input

第一行两个正整数 $$$n,k\ (2\le n\le5\times 10^5,0\le k\le n-2)$$$，第二行一个字符串 $$$S$$$，意义见题目描述。$$$S$$$ 仅由英文小写字母构成。

Output

输出一行一个整数表示答案。

Examples
Input
5 1
aabcc
Output
11
Input
6 2
aaaaaa
Output
19
Input
8 1
aabaabcd
Output
27
Note

对于第一组样例，有以下 $$$11$$$ 种方案：

  • $$$A = a, \quad B_1 = a, \quad C = bcc, \quad i = 1, \quad j = 1$$$
  • $$$A = a, \quad B_1 = ab, \quad C = cc, \quad i = 1, \quad j = 1$$$
  • $$$A = a, \quad B_1 = abc, \quad C = c, \quad i = 1, \quad j = 1$$$
  • $$$A = aa, \quad B_1 = b, \quad C = cc, \quad i = 1, \quad j = 1$$$
  • $$$A = aa, \quad B_1 = bc, \quad C = c, \quad i = 1, \quad j = 1$$$
  • $$$A = aab, \quad B_1 = c, \quad C = c, \quad i = 1, \quad j = 1$$$
  • $$$A = a, \quad B_1 = ab, \quad C = c, \quad i = 1, \quad j = 2$$$
  • $$$A = a, \quad B_1 = b, \quad C = c, \quad i = 2, \quad j = 2$$$
  • $$$A = aa, \quad B_1 = b, \quad C = c, \quad i = 1, \quad j = 2$$$
  • $$$A = a, \quad B_1 = b, \quad C = cc, \quad i = 2, \quad j = 1$$$
  • $$$A = a, \quad B_1 = bc, \quad C = c, \quad i = 2, \quad j = 1$$$

E. 电梯
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

宁宁现在在建设大楼！

在宁宁的规划中，大楼有 $$$n$$$ 层，从下到上依次为第 $$$1, 2, \cdots, n$$$ 层，她还要建设 $$$m$$$ 个电梯，每个电梯一定会停在第 $$$1$$$ 层和第 $$$n$$$ 层，她可以选择让这些电梯停在中间某些层（也可以不停）。她希望建设的这 $$$m$$$ 个电梯满足：对于任意不同的两层 $$$x, y$$$，存在一个电梯使 $$$x, y$$$ 可以直达（中间不经过任何可以停的层）。为了降低建造成本，她希望电梯数 $$$m$$$ 尽量小。

宁宁她不太聪明，于是她转过来求助你，希望你能告诉她 $$$m$$$ 的最小值并给出构造。

你不需要最小化停的总层数。但还是为了节约资源，你需要使得停的总层数不超过 $$$2 \times 10^6$$$。

Input

一行一个正整数 $$$n$$$ $$$(2 \le n \le 1000)$$$。

Output

第一行一个正整数 $$$m$$$，表示最少需要的电梯数。

接下来 $$$m$$$ 行，每行表示一个电梯的停层状况。具体来说，对于第 $$$i$$$ 行，你需要输出一个序列 $$$a_{i, 1}, a_{i, 2}, \cdots, a_{i, k_i}$$$，使得 $$$1 = a_{i, 1} \lt a_{i, 2} \lt \cdots \lt a_{i, k_i} = n$$$，且 $$$\sum\limits_{i=1}^m k_i \le 2 \times 10^6$$$。表示第 $$$i$$$ 个电梯会停在 $$$a_{i, 1}, a_{i, 2}, \cdots, a_{i, k_i}$$$ 层。

输出量较大，建议采用较快的输出方式。

Example
Input
4
Output
4
1 3 4
1 4
1 2 3 4
1 2 4
Note

可以证明 $$$m$$$ 的最小值为 $$$4$$$。

第 $$$1, 2$$$ 层可以通过电梯 $$$3, 4$$$ 直达，第 $$$1, 3$$$ 层可以通过电梯 $$$1$$$ 直达，第 $$$1, 4$$$ 层可以通过电梯 $$$2$$$ 直达，第 $$$2, 3$$$ 层可以通过电梯 $$$3$$$ 直达，第 $$$2, 4$$$ 层可以通过电梯 $$$4$$$ 直达，第 $$$3, 4$$$ 层可以通过电梯 $$$1, 3$$$ 直达。

F. 猜01序列
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

这是一道交互题。

给定正整数 $$$n$$$，评测机会生成一个未知的长度为 $$$n$$$ 的 $$$\texttt{01}$$$ 序列 $$$a_1,a_2,\dots,a_n$$$，你最多可以问评测机 $$$17$$$ 个问题，来求解这个 $$$\texttt{01}$$$ 序列中 $$$\texttt{1}$$$ 的个数，即 $$$\sum\limits_{i=1}^n a_i$$$。数据保证至少有一个 $$$\texttt{1}$$$。

对于每一次询问，你可以选择若干个位置 $$$i_1,i_2,\dots,i_k$$$，设 $$$I=\{i_1,i_2,\dots,i_k\}$$$，评测机会返回 $$$(\sum\limits_{j\in I} a_j) \cdot (\sum\limits_{j\notin I} a_j)$$$ 的结果。

Input

第一行一个正整数 $$$n$$$ $$$(1\le n\le 10^5)$$$，表示这个 $$$\texttt{01}$$$ 序列的长度。

Interaction

对于询问，请按以下格式输出一行（不包括引号）：

"$$$?\ k\ i_1\ i_2\ \dots\ i_k$$$" $$$(1\le k\le n,1\le i_1 \lt i_2 \lt \dots \lt i_k\le n)$$$。

对于输出答案，请按以下格式输出一行（不包括引号）：

"$$$!\ s$$$"，其中 $$$s=\sum\limits_{i=1}^n a_i$$$。

输出答案本身不计入查询次数。

交互器是非自适应的，也就是说，答案在参与者提出任何查询之前就已经确定了，并且不会依赖于参与者所提出的查询。

在输出每个查询之后，不要忘记输出换行并刷新输出缓冲区。

你可以使用如下语句来清空缓冲区：

  • 对于 C/C++：fflush(stdout)
  • 对于 C++：std::cout <{}< std::flush
  • 对于 Java：System.out.flush()
  • 对于 Python：sys.stdout.flush()
Examples
Input
3

2
Output

? 2 1 3

! 3
Input
3

0

0
Output

? 1 1

? 1 2

! 1
Note

第一个样例隐藏的数列为 $$$[1,1,1]$$$，第二个样例隐藏的数列为 $$$[0,1,0]$$$

G. 建设高铁
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A国要举办世界杯了！

为了迎接世界杯的到来，A国打算修建高铁连接所有举办城市。（A国目前还没有修建高铁）

A国有 $$$n$$$ 个城市，$$$m$$$ 条线路有条件修建高铁，每条线路有各自的修建难度系数。

为了更好地施工，A国打算进口一台高级设备。但由于经费紧张，只能进口一台。如果进口了一台价格为 $$$V$$$ 的设备，那么该设备可以修所有难度系数不超过 $$$V$$$ 的路线。

此外，每个城市有一个繁荣程度。为了展现国家实力，A国肯定要在最繁荣的几个城市举办比赛。但随着时间的推移，每个城市的繁荣程度也在不断发生变化。

作为A国元首，你想知道，在当前局面下，若选择最繁荣的 $$$k$$$ 个城市举办比赛，想用高铁连接这些城市，至少需要花费多少经费（购买设备）。

Input

第一行三个正整数 $$$n,m,q$$$ $$$(1\le n,q\le 5\times 10^5; n-1\le m \le \min\{\frac{n(n+1)}{2},5\times 10^5\})$$$，分别表示城市的数量，线路的数量，询问的次数。

第二行 $$$n$$$ 个正整数 $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i \le 10^9)$$$，表示每个城市的繁荣程度。

接下来 $$$m$$$ 行，每行三个正整数 $$$x_i,y_i,d_i$$$ $$$(1\le x_i,y_i\le n; x_i \neq y_i; 1\le d_i \le 10^9)$$$，分别表示第 $$$i$$$ 条线路连接的两个城市的编号，以及该线路修建的难度系数。保证图联通，无重边自环。

接下来 $$$q$$$ 行，每行先输入一个正整数 $$$op_i$$$ $$$(1\le op_i\le 2)$$$。

如果 $$$op_i=1$$$，则接下来输入两个正整数 $$$c_i,t_i$$$ $$$(1\le c_i\le n;1\le t_i\le 10^9)$$$，表示编号为 $$$c_i$$$ 的城市繁荣程度变为了 $$$t_i$$$；

如果 $$$op_i=2$$$，则接下来输入一个正整数 $$$k_i$$$ $$$(1\le k_i\le n)$$$，询问当前局面下选择最繁荣的 $$$k_i$$$ 个城市举办比赛，至少需要花费多少经费。（如果两个城市的繁荣程度相同，则优先选择编号较小的城市）。

Output

对于每个询问，输出一行一个正整数表示答案。

Example
Input
4 4 8
4 3 2 1
1 2 4
3 2 1
3 4 2
4 1 3
2 2
1 3 4
1 4 4
2 2
1 3 5
1 4 6
2 2
2 1
Output
3
3
2
0

H. 可能是字符串签到题
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$（仅由小写字母组成，下标从 $$$1$$$ 开始），进行 $$$q$$$ 次询问，每次询问给出两个整数 $$$l,r$$$，询问子串 $$$s[l,r]$$$ 中出现次数最多的子串出现了多少次。

注：字符串 $$$s$$$ 的子串定义为 $$$s$$$ 中连续且顺序一致的一段字符序列，即对于下标 $$$l, r$$$ $$$(1 \le l \le r \le |s|)$$$，子串 $$$s[l,r]$$$ 表示为 $$$s_l s_{l+1} \dots s_r$$$。

Input

第一行输入两个整数 $$$n,q(1\le n,q\le 10^6)$$$，分别表示字符串长度和查询次数。

第二行输入一个字符串 $$$s$$$，仅由小写字母组成。

接下来 $$$q$$$ 行，每行两个整数 $$$l,r(1 \le l\le r \le n)$$$，表示查询子串的下标。

Output

对于每个询问，输出一行一个整数，表示出现次数最多的子串出现了多少次。

Example
Input
5 2
ababa
1 4
4 5
Output
2
1
Note

样例解释：

对于第一组询问，子串 $$$\text{ab}$$$ 在 $$$\text{abab}$$$ 中出现了 $$$2$$$ 次，没有出现次数更多的子串。

I. 山海关老冰糕
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

冰凉清甜的老冰糕是山海关特色。老冰糕工厂里有 $$$N$$$ 台生产线，第 $$$i$$$ 台生产线生产一份老冰糕需要耗时 $$$t_i$$$ 分钟。所有生产线同时开工，且可以并行工作。

现在工厂接到了一个巨大的夏日订单，需要在最短的时间内生产出至少 $$$M$$$ 份老冰糕。请问工厂最少需要多少分钟才能完成订单？

Input

第一行包含两个整数 $$$N$$$ 和 $$$M$$$ ($$$1 \le N \le 10^5, 1 \le M \le 10^{12}$$$)，分别表示生产线数量和订单需求量。

第二行包含 $$$N$$$ 个整数 $$$t_1, t_2, \dots, t_N$$$ ($$$1 \le t_i \le 10^6$$$)，表示每条生产线生产一根冰棍的耗时。

Output

输出一个整数，表示完成订单所需的最少分钟数。

Example
Input
3 10
2 3 5
Output
10

J. 海鲜大排档点生蚝
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

秦皇岛的海鲜大排档里，生蚝既可以按整打购买，也可以按单个购买。

第 $$$i$$$ 家摊位，单买价格为 $$$A_i$$$ 元/个，整打价格为 $$$B_i$$$ 元/打（1 打 = 12 个）。

你有 $$$M$$$ 元钱，并且只能选择其中一家摊位进行购买。

在同一家摊位中，你可以买若干打生蚝，再单买若干个生蚝，两种购买方式可以混合使用。

请你求出在最优购买策略下，最多可以买到多少个生蚝。如果有多家摊位都能达到最大数量，输出编号最小的摊位。

Input

第一行包含两个整数 $$$N, M\ (1 \le N \le 10^5,\quad 1 \le M \le 10^9)$$$，表示摊位数量和预算。

接下来 $$$N$$$ 行，每行两个整数 $$$A_i, B_i\ (1 \le A_i, B_i \le 10^5)$$$，分别表示第 $$$i$$$ 家摊位的单买价格和整打价格。

Output

输出两个整数，表示最多能买到的生蚝数量和选择的摊位编号，若有多个答案，输出编号最小的。

Example
Input
10 100
3 192
5 185
20 84
12 86
16 101
1 37
7 170
16 98
16 22
20 84
Output
100 6

K. 灯带
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

五月二十四日，是小 X 的生日。为了庆祝他的生日，他的朋友们为他准备了一个生日聚会。这个聚会上有一样非常重要的道具——灯带。这个灯带上需要放 $$$n$$$ 个灯（不能有位置不放），每个灯可以是红、绿、蓝三种颜色之一。为了尽可能地降低成本，朋友们只分别准备了 $$$r, g, b$$$ 个红、绿、蓝色灯，且恰好一共准备了 $$$n$$$ 个灯。

但是，小 X 对灯带是有自己的喜好的。具体来说，他的喜好包含 $$$m$$$ 对数 $$$(l_1, r_1), \dots, (l_m, r_m)$$$，他希望对于每一个 $$$i$$$，第 $$$l_i \sim r_i$$$ 个灯当中包含最多两种不同的颜色。保证对任意 $$$1 \le i \le m$$$，都有 $$$1 \le l_i \le r_i \le n$$$，且对任意 $$$1 \le i \lt j \le m$$$，都有 $$$r_i \lt l_j$$$ 或者 $$$r_j \lt l_i$$$（即区间 $$$[l_i, r_i]$$$ 和 $$$[l_j, r_j]$$$ 不交）。

现在小 X 的朋友们需要构造一个方案满足小 X 的喜好。但准备的灯实在是太多了，朋友们很难很快想出一种方案，于是来求助于会编程的你。请你帮帮他们，构造一种满足小 X 的喜好的灯带方案，或者告诉他们方案不存在。

Input

本题包含多组数据。

第一行一个整数 $$$T$$$ $$$(1 \le T \le 10^5)$$$，表示数据组数。

对于每组数据：

第一行两个正整数 $$$n, m, r, g, b$$$ $$$(1 \le m \le n \le 10^5, 0 \le r, g, b \le n, r+g+b=n)$$$，分别表示灯带长度和小 X 喜好对应的 $$$(l, r)$$$ 数量，以及红、绿、蓝色灯的数量。

接下来 $$$m$$$ 行，第 $$$i$$$ 行包含两个正整数 $$$l_i, r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$。保证对任意 $$$1 \le i \lt j \le m$$$，都有 $$$r_i \lt l_j$$$ 或者 $$$r_j \lt l_i$$$。

保证每组数据的 $$$n$$$ 的和不超过 $$$2 \times 10^5$$$。

Output

对于每组数据，如果方案存在，则输出包含一行一个只由 R, G, B 构成的长度为 $$$n$$$ 字符串，其中 R, G, B 分别表示红、绿、蓝色灯，表示方案。你需要保证字符串当中 R, G, B 的数量分别恰好是每组数据对应的 $$$r, g, b$$$。若方案不存在，则输出 $$$-1$$$。

Example
Input
3
3 2 1 1 1
1 2
3 3
4 1 1 1 2
1 3
6 1 2 2 2
1 5
Output
BGR
BBGR
-1

L. 贪吃蛇
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

夏天到了，又到了蛇蛇出来觅食的季节。

蛇蛇生活的地方可以看成一个二维平面，它位于原点 $$$(0,0)$$$。平面上有 $$$n$$$ 个食物，第 $$$i$$$ 个食物位于整数坐标 $$$(x_i,y_i)$$$，保证没有食物位于原点。

蛇蛇的觅食方式很特殊：

  1. 先选择一个以原点为圆心的角度区间 $$$[\alpha,\beta]$$$；
  2. 以原点为顶点，张开一个以该区间为圆心角的扇形，并且扇形会不断向外扩展，直到将该角度区间内（包含边界）的所有食物全部一口吞下。

扇形的面积大小就是蛇蛇本顿觅食消耗的能量。

蛇蛇现在很饿，它想知道，想要一口吃掉至少 $$$k$$$ 个食物，所需的最少能量是多少？

Input

第一行一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$)，表示测试数据组数。保证所有测试数据的 $$$n$$$ 之和不超过 $$$2\times 10^5$$$。

对于每组数据：

第一行两个整数 $$$n,k$$$ ($$$1\le k\le n\le 2\times 10^5$$$)，分别表示食物总数和至少需要吃掉的食物数量。

接下来 $$$n$$$ 行，每行两个整数 $$$x_i,y_i$$$ ($$$|x_i|,|y_i|\le 10^6$$$)，表示第 $$$i$$$ 个食物的坐标。保证 $$$(x_i,y_i)\neq(0,0)$$$。

Output

对于每组数据，输出一行一个实数，表示最少所需能量。

当你的输出与标准答案的绝对误差或相对误差不超过 $$$10^{-9}$$$ 时即被视为正确。

Example
Input
2
1 1
1 2
3 2
0 2
1 0
-1 -1
Output
0.000000000000
2.356194490192
Note

对于第一组数据，只有一个食物且 $$$k=1$$$，选择的角度区间恰好只包含该食物的方向，扇形退化为一条从原点出发的线段，面积为 $$$0$$$。

对于第二组数据，最优策略为覆盖食物 $$$(-1,-1)$$$ 和 $$$(1,0)$$$，最少能量是 $$$\frac{1}{2} \times \frac{3\pi}{4} \times 2 = \frac{3\pi}{4}$$$。

M. 拯救猫猫
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

库若猫误入了狗群守护的街区，他需要你的帮助!

街区是一个 $$$n \times m$$$ $$$(1 \le n,m \le 2000)$$$ 的网格。每个格子可能是空地、障碍物或狗。每只狗朝向固定的方向（上、下、左或右），它的视线会沿其正前方延伸，直到被障碍物或另一只狗阻挡。

库若猫被困在起点 $$$S$$$，必须从街区出口 $$$E$$$ 逃脱，他的移动遵循以下规则：

  • 每一步只能移动到相邻的四个空格（上、下、左、右）之一

  • 不能跨越网格边界

  • 不能进入任何狗的视线范围内

  • 不能经过狗或障碍物所在的格子

你可以让一只狗睡着。睡着的狗会失去视线，但库若猫仍然不能经过它。请判断是否存在一种方案，使得库若猫能够顺利到达出口；如果存在，找出这只狗的坐标。

保证网格中至少存在一只狗，起点 $$$S$$$ 和出口 $$$E$$$ 是空地且不在任何狗的视线内

Input

每个测试文件包含多组测试数据。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) 表示测试数据的数量。

每个测试数据的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2000$$$) ，表示网格的行数和列数。

接下来的 $$$n$$$ 行，每行包含一个长度为 $$$m$$$ 的字符串，表示街区的布局：

  • (.) 表示空地
  • (#) 表示障碍物
  • (E) 表示街区出口
  • (S) 表示库若猫的起点
  • (U), (D), (L), (R) 表示朝向分别为上，下，左，右的狗

保证所有测试数据中 $$$n$$$ 和 $$$m$$$ 的总和均不超过 $$$2000$$$

Output

对于每组测试数据：

如果不存在让库若猫逃脱的方案，输出用空格分隔的两个 $$$-1$$$ 。

否则，输出用空格分隔的整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x \le n$$$, $$$1 \le y \le m$$$)，表示被选定睡着的狗的行坐标和列坐标。如果存在多种方案，优先选择行坐标 $$$x$$$ 最小的方案；若行坐标相同，优先选择列坐标 $$$y$$$ 最小的方案。

Example
Input
3
7 7
.D....E
...#..L
..#...L
.#.L..D
....#..
#.L....
S...#.L
3 3
..E
R.L
S..
4 4
.D.E
....
.D..
S...
Output
1 2
-1 -1
1 2
Note

网格的行从上到下编号为 $$$1$$$ 到 $$$n$$$，列从左到右编号为 $$$1$$$ 到 $$$m$$$