Danimal Cannon, Zef - The Lunar Whale⠀

You are the security guard of a museum.

The main door of the museum is both an entrance and an exit. At most one person can pass through the door every second. There is a sensor that detects when a visitor passes through the door. The sensor cannot determine neither who the visitor is, nor whether he entered or exited the museum. The sensor detected some activity in $2n$ distinct moments of time $a_1, a_2, \ldots, a_{2n}$ (measured in seconds).

For each visitor, his stay time is equal to the exit time minus the entrance time.

Right now the museum is closed (so it has no visitors), and you wonder about the maximum possible total stay time today, i.e., the maximum possible sum of the stay times of all the visitors that entered the museum today. At second $0$, the museum was closed as well.

For security reasons, there is also a limit on the number of people who can stay in the museum simultaneously, but you forgot this limit. For each $k$ from $1$ to $n$, you want to determine the maximum possible total stay time today, assuming that at most $k$ people can stay in the museum simultaneously.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), indicating that the sensor detected some activity in $2n$ distinct moments of time.

The second line of each test case contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \leq a_1 \lt a_2 \lt \ldots \lt a_{2n} \leq 10^9$) — the seconds when the sensor detected some activity.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, print $n$ integers: for each $k$ from $1$ to $n$, print the maximum possible total stay time today, assuming that at most $k$ people can stay in the museum simultaneously.

Note

In the first test case, the sensor detected activity at seconds $32$ and $78$. Recall that $k$ is the maximum number of people who can stay in the museum simultaneously.

• If $k$ is $1$, the maximum possible total stay time is $46$, reached if visitor $1$ enters at time $32$ and exits at time $78$.

In the second test case, the sensor detected activity at seconds $4$, $5$, $6$, and $9$.

• If $k$ is $1$, the maximum possible total stay time is $4$, reached if visitor $1$ enters at time $4$ and exits at time $5$, and visitor $2$ enters at time $6$ and exits at time $9$.
• If $k$ is $2$, the maximum possible total stay time is $6$, reached if visitor $1$ enters at time $4$ and exits at time $9$, and visitor $2$ enters at time $5$ and exits at time $6$.