Problem E
Diamantes sensíveis

João o joalheiro é um ambicioso comerciante que vende diamantes para diferentes tipos de clientes e, para atender a variada demanda, comercializa diamantes de tamanhos variados. Embora sua rede de negócios seja bastante vasta, ele não é o vendedor mais cuidadoso e muitas vezes ao guardar diamantes novos no estoque, acaba quebrando diamantes que estavam lá previamente.

O estoque de João é tão enorme que pode ser abstraído pelo semiplano infinito de $y \geq 0$ onde os diamantes são postos no chão (eixo $x$). Cada diamante pode ser representado como um quadrado rotacionado em $45$ graus em relação a um quadrado de lados paralelos aos eixos coordenados. Os diamantes tocam o chão (eixo $x$) com um de seus vértices e todos seus demais pontos tem coordenada $y$ positiva.

João recebe $n$ diamantes, que são postos no armazém um depois do outro e são numerados de $1$ a $n$ pela ordem do input. O $i$-ésimo diamante é definido por $x_ i$ e $y_ i$, seu centro.

Para cada diamante posto você deve dizer quantos e quais diamantes previamente encontrados no armazém o último diamante quebra, ou seja, quais diamantes que não foram quebrados ainda e cuja interseção com o diamante recém posto tem área não nula (note que quando um diamante é posto no armazém ele não é quebrado mesmo que quebre outros diamantes, e os diamantes que são quebrados não devem ser considerados pelos diamantes postos a seguir).

Input

A primeira linha do input conterá um inteiro $n$ ($2 \leq n \leq 100\, 000$), o número de diamantes armazenados por João. Seguirão $n$ linhas, numeradas de $1$ a $n$ na ordem em que são dadas, a $i$-ésima contém dois inteiros $x_ i$ e $y_ i$ ($-1\, 000\, 000\, 000 \leq x_ i \leq 1\, 000\, 000\, 000, 1 \leq y_ i \leq 1\, 000\, 000\, 000$) o centro do diamante de número $i$.

Output

Imprima $n$ linhas, onde em cada linha, o primeiro inteiro é $q_ i$, a quantidade de diamantes quebrados na $i$-ésima inserção seguido por $q_ i$ inteiros, os índices, numerados de $1$ a $n$ pela ordem em que são lidos no input, em ordem crescente dos diamantes anteriores quebrados pelo $i$-ésimo diamante.

4
-1 1
1 1
1 2
0 1

0
0
1 2
2 1 3