Petra 和 Jan 刚刚收到了一盒免费的物品，并想把这些物品分掉。然而，要公平地进行分配并不容易，因为他们对不同物品的估值是不同的。

为了分配物品，他们决定采用以下步骤：轮流逐个选择物品，直到所有物品都被选完。通过抛硬币来决定谁先开始选第一个物品。

Petra 和 Jan 在决定选择什么时有着不同的策略。当面临选择时，Petra 总是选择对她而言价值最高的物品。如果出现平局（即有多个物品对她的价值相同且最高），她会非常体贴地选择对 Jan 而言价值最低的那一个。（由于 Petra 和 Jan 是好朋友，他们完全清楚对方对每个物品的估值。）

然而，Jan 的策略是最大化他自己最终获得的总价值。他同样非常体贴，因此如果多种选择都能带来相同的最优结果，他会优先选择能让 Petra 获得尽可能多最终价值的方案。

现在给你初始抛硬币的结果。在 Jan 和 Petra 分完所有物品后，他们每个人最终获得的物品总价值分别是多少？

输入格式

第一行包含一个正整数：测试用例的数量，最多为 $100$。对于每个测试用例：

• 一行包含一个整数 $n$ ($1 \le n \le 1\,000$)：物品的数量。
• 一行包含一个字符串，为 "Petra" 或 "Jan"：代表先选物品的人。
• $n$ 行，每行包含两个整数 $p_i$ 和 $j_i$ ($0 \le p_i, j_i \le 1\,000$)：分别代表 Petra 和 Jan 对第 $i$ 个物品的估值。

输出格式

对于每个测试用例：

• 输出一行，包含两个整数：Petra 获得的价值和 Jan 获得的价值。两个价值都必须根据他们各自的估值来计算。

样例

样例输入 1

3
4
Petra
100 80
70 80
50 80
30 50
4
Petra
10 1
1 10
6 6
4 4
7
Jan
4 1
3 1
2 1
1 1
1 2
1 3
1 4

样例输出 1

170 130
14 16
9 10