在四面无边的格子田上有一个机器人。最初,机器人位于坐标为 $$$(0, 0)$$$ 的单元格中。他将执行由大写拉丁字母“L”、“R”、“D”、“U”字符串描述的命令。当执行命令时,机器人只是朝相应的方向移动:
- 'L':向左一个单元格(当前单元格的 $$$x$$$ 坐标减少 $$$1$$$);
- 'R':向右移动一个单元格(当前单元格的 $$$x$$$ 坐标增加 $$$1$$$);
- 'D':向下一个单元格(当前单元格的 $$$y$$$ 坐标减少 $$$1$$$);
- 'U':向上一个单元格(当前单元格的 $$$y$$$ 坐标增加 $$$1$$$)。
你的任务是在场地的一个单元格中放置一个障碍物,以便在执行命令后,机器人将返回到其路径 $$$(0, 0)$$$ 的原始单元格。当然,起始单元格$$$(0, 0)$$$中不能放置障碍物。保证如果没有放置障碍物,则机器人不会返回起始单元。
障碍物通过以下方式影响机器人的运动:如果它试图朝某个方向前进,并且存在障碍物,那么它只是保持在原地(障碍物也仍然存在,也就是说,它不会消失)。
找到任何这样的区域单元格($$$(0, 0)$$$ 除外),如果您在那里放置障碍物,机器人将在执行所有命令后返回到单元格 $$$(0, 0)$$$。如果没有解决办法,请报告。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。
每个测试用例都包含一行,其中包含 $$$s$$$ — 命令序列,仅是大写拉丁字母“L”、“R”、“D”、“U”。 $$$s$$$ 的长度介于 $$$1$$$ 和 $$$5000$$$ 之间(含边界值)。对 $$$s$$$ 的附加约束:如果没有障碍物,执行此命令序列会导致机器人到达 $$$(0, 0)$$$ 以外的某个单元格。
测试中所有 $$$s$$$ 的长度总和不超过 $$$5000$$$。
输出
对于每个测试用例打印一行:
- 如果有解决方案,则打印两个整数 $$$x$$$ 和 $$$y$$$ ($$$-10^9 \le x,y \le 10^9$$$),这样 $$$(x, y)$$$ 中的障碍物将迫使机器人返回单元格 $$$(0, 0)$$$;
- 否则,打印两个零(即 0 0)。
如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
4 L RUUDL LLUU DDDUUUUU
输出 #1
-1 0 1 2 0 0 0 1