Bob 是一位商人，Alice 是他的助手。他们计划在 $n$ 个城市收集原材料，然后在其中一个城市会合，加工并销售产品。

具体来说，他们的计划由以下步骤决定：

• 首先，Alice 将 $n$ 个城市排列成任意顺序，得到城市序列 $p_1, p_2, \dots, p_n$（一个排列）。
• 然后，Bob 在 $n$ 个城市中选择一个会合城市。也就是说，Bob 会选择一个整数 $m(1 \le m \le n)$，并将城市 $p_m$ 作为会合城市。
• 接下来，他们从城市序列的两端开始工作。Alice 前往城市 $p_1, p_2, \dots, p_m$ 收集原材料，Bob 前往城市 $p_n, p_{n-1}, \dots, p_m$ 收集原材料。

最后，Alice 和 Bob 将在城市 $p_m$ 会合，并加工所有原材料以生产产品（一份原材料恰好可以生产一份产品）。之后，他们会在城市 $p_m$ 销售所有产品。他们的最终收入可以通过以下信息计算：

• 如果城市 $i$ 由 Alice 访问，则 Alice 将收集 $a_i$ 份原材料。
• 如果城市 $i$ 由 Bob 访问，则 Bob 将收集 $b_i$ 份原材料。
• 在城市 $i$ 销售的每份产品将获得 $c_i$ 金币。
• 众所周知，该计划的总收入为 $(\sum_{i=1}^m a_{p_i} + \sum_{i=m}^n b_{p_i}) \cdot c_{p_m}$ 金币。

Bob 非常想赚钱，所以当他选择会合城市 $p_m$ 时，他会尽量使总收入尽可能大。

Alice 知道 Bob 很贪婪，所以她了解 Bob 选择会合城市的策略。然而，Bob 经常虐待 Alice，这让 Alice 很不高兴。因此，在第一步中，Alice 希望最终计划的总收入尽可能小。

你能帮 Alice 规划城市序列吗？请输出城市序列 $p_1, p_2, \dots, p_n$，使得最终计划的总收入尽可能小。

输入格式

每个测试数据包含多个测试用例。 第一行包含一个正整数 $T$，表示测试用例的数量。 对于每个测试用例：

• 第一行包含一个整数 $n(1 \le n \le 10^5)$，表示城市的数量。
• 接下来的 $n$ 行，第 $i$ 行包含 3 个整数，表示第 $i$ 个城市的信息 $a_i, b_i, c_i(1 \le a_i, b_i, c_i \le 10^6)$，其含义如上所述。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。即 $\sum n \le 10^5$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示 Alice 规划的顺序，使得总收入尽可能小。如果有多种方案，输出任意一种即可。

样例

输入 1

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

输出 1

3 1 2 4
3 8 4 2 5 9 7 1 6