동전

동전 묶음이 $n$개 있고, $i$번째 묶음에는 가치가 각각 $a_i$, $b_i$인 동전 두 개가 들어 있다. 이 중에서 동전을 정확히 $k$개 고르려고 한다. 단, 제약이 하나 있다. $i$번째 묶음의 두 번째 동전(가치 $b_i$)은 같은 묶음의 다른 동전을 함께 고를 때에만 고를 수 있다. 즉, $i$번째 묶음에서는 다음 중 하나를 고를 수 있다.

• 두 동전을 모두 고르지 않는다.
• 가치 $a_i$인 동전만 고른다.
• 두 동전을 모두 고른다.

정확히 $k$개의 동전을 고를 때 가치의 합의 최댓값을 $f(k)$라고 하자.

$f(1), f(2), \ldots, f(2n)$의 값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 개수 $T$ ($1 \le T \le 90$)가 주어진다.

각 테스트 케이스의 첫 줄에는 동전 묶음의 개수 $n$ ($1 \le n \le 100000$)이 주어진다.

이후 $n$개의 줄에 각각 두 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le 10000$)가 주어지며, 이는 해당 묶음의 동전 가치이다.

모든 테스트 케이스에 대한 $n$의 합은 $2100000$을 넘지 않는다.

각 테스트 케이스마다 $2n$개의 정수를 한 줄에 출력한다. 출력할 값은 $f(1), f(2), \ldots, f(2n)$이다. 연속된 정수는 공백 한 칸으로 구분한다.