三维分界（divider）

题目描述

Y 同学正在评估一批设备。第 $i$ 台设备记录了三项指标 $(a_i,b_i,c_i)$。

现在需要先将所有设备按照如下规则排序：

1. 按 $a$ 从大到小排序；
2. 若 $a$ 相同，按 $b$ 从大到小排序；
3. 若 $a,b$ 都相同，按 $c$ 从小到大排序；
4. 若仍相同，按原编号从小到大排序。

排序后得到序列 $p_1,p_2,\dots,p_n$。

称位置 $k$（$1 \le k \le n$）是一个有效分界，当且仅当同时满足以下三个条件：

• 在前缀 $[1,k]$ 中，设备 $p_k$ 的 $b$ 严格大于此前所有设备的 $b$；
• 在前缀 $[1,k]$ 中，设备 $p_k$ 的 $c$ 严格小于此前所有设备的 $c$；
• 不允许拆开同一吞吐评分组。也就是说，若 $k < n$，必须满足 $a_{p_k} > a_{p_{k+1}}$。

请你输出所有有效分界位置 $k$，并输出有效分界的个数。

输入格式

第一行输入一个整数 $T$，表示测试组数。

对于每组测试数据：

• 第一行输入一个整数 $n$；
• 接下来 $n$ 行，每行输入三个整数 $a_i,b_i,c_i$。

输出格式

对于每组测试数据：

• 第一行输出一个整数，表示有效分界个数；
• 第二行按从小到大输出所有有效分界位置 $k$；
• 若不存在有效分界，则第二行输出 None。

样例

样例输入 #1

1
7
100 60 30
95 80 28
95 78 35
92 85 25
90 84 18
88 90 22
80 91 15

样例输出 #1

3
1 4 7

样例解释 1

样例一中各设备已经按题目要求排好序，因此排序后的序列不变。

依次考察各个位置：

其中，位置 $2$ 虽然满足前两条，但由于它与下一台设备的吞吐评分相同，都是 $95$，不能把同吞吐评分组拆开，因此不计入答案。

所以所有有效分界位置为：${1,4,7}$

样例输入 #2

1
6
90 70 40
100 50 30
95 80 28
95 75 20
88 90 18
92 85 25

样例输出 #2

2
1 6

样例解释 2

排序后，得到序列：

再依次判断各个位置：

其中：

• 位置 $2$ 虽然满足前两条，但由于下一台设备的吞吐评分仍为 $95$，不能把同一吞吐评分组拆开，所以不能作为分界；
• 位置 $6$ 是末尾位置，只要前两条满足即可。

因此所有有效分界位置为：${1,6}$

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 10$，$1 \le n \le 2 \times 10^5$，$1 \le a_i,b_i,c_i \le 10^9$，且所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

• 特殊性质 A：保证所有设备的 $a_i$ 两两不同。
• 特殊性质 B：保证输入顺序与题目要求的排序结果完全一致。
• 特殊性质 C：保证所有设备的 $a_i$ 都相同。