407825: GYM102897 L 咆哮

L. 咆哮time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

lanChe 最近迷上了三国杀国战。其中有一局，使用了如下两个英雄大杀四方。

$$$\qquad$$$ lanChe 在其中一回合中杀穿了 $$$4$$$ 个人，并且想把这份喜悦分享给你们。但这一局的情况说不清楚，便换个思路把喜悦分享给你们。

现在 lanChe 处于鏖战当中。根据国战的规则，鏖战时候不能使用桃进行回血，改成把桃当成杀或者闪。

lanChe 上回合惹怒了对面两个阵营, 现在吴国和群国联合起来对抗蜀国。对面 $$$2$$$ 名角色的阵容如下：

$$$\qquad$$$ $$$\qquad$$$

这场鏖战如宁所料，将会是场美丽的世界名画。为了赢取蜀国的最终胜利，lanChe 现在想知道，他将要承受多少伤害。现在假设一下，假设在第 $$$x$$$ 轮， lanChe 在这个回合内最终能拿到 $$$x$$$ 张杀，为简化起见，现规定每轮的杀全部出完，并且只能选一名角色。

给出吴国阵营的血量 $$$HP_w$$$ 和他每轮对蜀国造成的固定伤害值 $$$ATK_w$$$ ,以及群国阵营的血量 $$$HP_q$$$ 和他每轮对蜀国造成的固定伤害值 $$$ATK_q$$$ 。

一旦某国阵营血量 $$$\leq 0$$$ ，直接出局，下轮不再对蜀国造成伤害。

现在 lanChe 想知道赢取蜀国的胜利最少需要承受多少伤害。

并且制定一份攻击策略使得自身承受的伤害最小。策略的格式为：

• 第 $$$i$$$ 轮若攻击吴国阵营，则在第 $$$i$$$ 位输出 "W"。
• 第 $$$i$$$ 轮若攻击群国阵营，则在第 $$$i$$$ 位输出 "Q"。

例如，在第 $$$1$$$ 轮攻击吴国，第二轮攻击群国，则输出字符串 "WQ"。

lanChe 现今在苦苦防守当中，没心思去思考这份完美的策略，便请求你的帮助。

答案输出最终承受的最小伤害以及相应的策略。若有多份策略，请输出字典序最小的策略。

Input

第一行输入 $$$T(1 \leq T \leq 10^4)$$$ ,代表有 $$$T$$$ 组数据。

接下来 $$$T$$$ 行，每行有四个正整数 $$$HP_q$$$, $$$HP_w$$$, $$$ATK_q$$$, $$$ATK_w$$$, 表示群国当前的血量，吴国当前的血量，群国对蜀国造成的伤害以及吴国对蜀国造成的伤害。$$$(1 \leq HP_q,\;HP_w,\;ATK_q,\;ATK_w \leq 10^9)$$$。

Output

对于每组数据，输出一行，表示蜀国赢取胜利需要承受的最小伤害值以及蜀国的攻击策略，两者之间以空格间隔。

若有多种策略选择，则输出字典序最小的策略。

ExampleInput

2
3 3 5 15
4 2 1 100

Output

45 WWQ
203 QWQ

Note

字典序的定义：按照第一个字母, 以 a、b、c..z 的顺序排列。如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如 sigh 和 sight），那么把短者排在前。

$$$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$$$——源自百度百科