#P7784. King of Hot Pot

King of Hot Pot

King of Hot Pot

Problem Description

Little Q is enjoying hot pot together with Tangjz. There are nn dishes of meat in the boiling water, labeled by 1,2,…,n1,2,\dots,n. The ii-th dish of meat will be OK to eat at time aia_i, and it will take Little Q bib_i units of time to swallow it. It is impossible for Little Q to swallow more than one dish of meat at the same moment. Note that for the ii-th dish of meat, Little Q can choose to ignore it for a while and swallow it later. Little Q is called "King of Hot Pot", and he wants to show off before Tangjz by swallowing kk dishes of meat as soon as possible. Please write a program to help Little Q find kk dishes of meat and the order to swallow them such that the time he spends on reaching the target is minimized for every possible value of kk (1≤k≤n1\leq k\leq n). Note that the time for waiting is also included in the answer.

Input

The first line of the input contains a single integer TT (1≤T≤10 0001 \leq T \leq 10\,000), the number of test cases. For each case, the first line of the input contains an integer nn (1≤n≤300 0001 \leq n \leq 300\,000), denoting the number of dishes of meat. Each of the following nn lines contains two integers aia_i and bib_i (1≤ai,bi≤1091\leq a_i,b_i\leq 10^9), denoting each dish of meat. It is guaranteed that the sum of all nn is at most 1 000 0001\,000\,000.

Output

For each test case, output a single line containing nn integers, the kk-th (1≤k≤n1\leq k\leq n) of which denoting the minimum possible units of time needed for Little Q to swallow kk dishes of meat.

Sample Input

1
5
1 2
4 6
3 5
4 2
3 2

Sample Output

3 5 7 12 18

Source

2020 Multi-University Training Contest 2