E. Revenge on My Boss
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob is a businessman and Alice is his assistant. They planned to collect the raw materials in $$$n$$$ cities, and then meet in one of the cities to process and sell the products.

Specifically, their plan is determined by the following steps:

  • First, Alice arranges the $$$n$$$ cities in any order to get the city sequence $$$p_1,p_2,\cdots p_n$$$(a permutation).
  • Then, Bob selects a meeting city among the $$$n$$$ cities. That is, Bob will select an integer $$$m(1\le m\le n)$$$ and then use the city $$$p_{m}$$$ as the meeting city.
  • Next, they work from both ends of the city sequence. Alice goes to city $$$p_1,p_2\cdots p_m$$$ for raw material collection, and Bob goes to city $$$p_n,p_{n-1},\cdots p_m$$$for raw material collection.
Finally, Alice and Bob will meet at city $$$p_m$$$ and process all the raw materials to produce products(one material can be used to produce exactly one product). After that they will sell all the products in the city $$$p_m$$$. Their final income can be calculated using the following information:
  • If the city $$$i$$$ is visited by Alice, then $$$a_i$$$ raw materials will be collected by Alice.
  • If the city $$$i$$$ is visited by Bob, then $$$b_i$$$ raw materials will be collected by Bob.
  • Each product sold in the city $$$i$$$ will earn $$$c_i$$$ gold.
  • All can know, the total income of the plan is $$$\big(\sum_{i=1}^{m} a_{p_i} + \sum_{i=m}^{n} b_{p_i}\big)\cdot c_{p_m}$$$ gold.
Bob really wants to make money, so when he selects the meeting city $$$p_m$$$, he must try to make the total income as large as possible.

Alice knows Bob is greedy, so she knows Bob's strategy for choosing the meeting city. However, Bob often mistreats Alice, which makes Alice unhappy. So in the first step, Alice wants that the total income of the plan is as small as possible finally.

Can you help Alice plan the city sequence? Please output the city sequence $$$p_1,p_2,\cdots p_n$$$ to make the finally total income of the plan as small as possible.

Input

Each test data of this problem has multiple cases.

The first line contains an positive integer $$$T$$$, indicating the number of cases.

For each case:

  • The first line contains an integer $$$n(1\le n\le 10^5)$$$ , indicating the number of cities.
  • For the next $$$n$$$ lines, the $$$i$$$-th line contains $$$3$$$ integers indicating the information of the $$$i$$$-th city, $$$a_i,b_i,c_i(1\le a_i,b_i,c_i\le 10^6)$$$, whose meanings are described above.

It is guaranteed that sum of $$$n$$$ over all cases is not greater than $$$10^5$$$. That is, $$$\sum n \le 10^5$$$.

Output

For each case, output a line, which contains $$$n$$$ integers, $$$p_1,p_2,\cdots p_n$$$, indicating the order planned by Alice to make the total income as small as possible. If there are multiple solutions, you can print any of them.

Example
Input
2
4
1 1 4
5 1 5
1 9 1
9 8 1
9
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 8
3 2 7
Output
3 1 2 4
3 8 4 2 5 9 7 1 6