切披萨

Problem Description

为了庆祝小 T 的生日，小 Q 定制了一张巨大的披萨，上面点缀着 $n$ 块糖果，编号依次为 $1,2,\dots,n$。披萨表面可以看作无限的平面直角坐标系，第 $i$ 块糖果位于（$x_i,y_i$），一个位置可能存在多块糖果。 小 T 将会进行 $m$ 次切披萨操作，第 $i$ 次操作将会沿直线 $ax+by=c$ 进行切割，拿走并吃掉直线碰到的以及直线下方的所有糖果，即所有满足 $ax+by\leq c$ 的糖果。 请写一个程序模拟每次切披萨操作，并汇报每次操作拿走了哪些糖果。

Input

第一行包含一个正整数 $T$（$1\leq T\leq 300$），表示测试数据的组数。 每组数据第一行包含一个正整数 $n$（$1\leq n\leq 200\,000$），表示糖果的数量。 接下来 $n$ 行，每行两个正整数 $x_i,y_i$（$1\leq x_i,y_i\leq 10^6$），分别表示每块糖果的坐标。 接下来一行包含一个正整数 $m$（$1\leq m\leq 200\,000$），表示切割的次数。 接下来 $m$ 行，每行三个正整数 $a,b,c$（$1\leq a,b\leq 10^6$, $1\leq c\leq 10^{12}$），依次描述每次切割。 输入数据保证 $\sum n\leq 1\,500\,000$ 且 $\sum m\leq 1\,500\,000$。

Output

对于每组数据输出 $m$ 行，第 $i$ 行首先输出一个整数 $k_i$，表示第 $i$ 次切割拿走的糖果数量，之后升序输出 $k_i$ 个正整数，依次表示每个本次被拿走的糖果的编号。

Sample Input

2
5
2 3
4 1
1 5
3 2
2 8
4
1 1 5
1 1 6
2 3 10
2 1 100
2
1 1
1 1
2
1 1 1
1 1 2

Sample Output

3 1 2 4
1 3
0
1 5
0
2 1 2

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）