有 $n$ 组硬币，第 $i$ 组包含两枚硬币，价值分别为 $a_i$ 和 $b_i$。现在你想从中恰好选出 $k$ 枚硬币。然而，有一个限制：如果不选第 $i$ 组中的第一枚硬币（价值为 $a_i$），就不能选该组中的第二枚硬币（价值为 $b_i$）。换句话说，对于第 $i$ 组，你可以：

• 不选这两枚硬币；
• 只选第一枚价值为 $a_i$ 的硬币；或者
• 两枚都选。

设 $f(k)$ 为选出恰好 $k$ 枚硬币时的最大总价值。 求 $f(1), f(2), \dots, f(2n)$ 的值。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 90$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示硬币组的数量。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10\,000$)，表示该组中硬币的价值。

保证所有测试用例中 $n$ 的总和不超过 $2\,100\,000$。

输出格式

对于每个测试用例，在单行内输出 $2n$ 个整数，依次表示 $f(1), f(2), \dots, f(2n)$。相邻整数之间用空格分隔。

样例

样例输入 1

2
3
1 2
1 4
4 2
2
1 3
3 2

样例输出 1

4 6 9 11 12 14
3 5 7 9