B. Board Game
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Danilo loves board games. Every weekend he meets his friends to play. However, after years of playing the same classic board games, he grew tired of them and hence decided to create his own game.

Danilo's game starts with $$$T$$$ tokens on the board, which can be seen as points in the two-dimensional plane. There are $$$P$$$ players that take a single turn each. In their turn, each player picks a card from a deck. The card describes a straight line, and the player gets all the tokens located strictly below this line. Tokens received by a player do not return to the board. Note that a token located at $$$(X,Y)$$$ is strictly below a line $$$y=A x + B$$$ if and only if $$$Y \lt A X + B$$$.

Given the list of cards, your task is to find which tokens each player receives.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) indicating the number of tokens on the board. Tokens are identified by distinct integers from $$$1$$$ to $$$T$$$. For $$${i}={1}, {2}, \ldots, {T}$$$, the $$$i$$$-th of the next $$$T$$$ lines contains two integers $$$X_i$$$ and $$$Y_i$$$ ($$$-10^9 \leq X_i, Y_i \leq 10^9$$$), denoting the coordinates of the token. No two tokens have the same location.

The next line contains an integer $$$P$$$ ($$$1 \leq P \leq 10^5$$$) representing the number of players in the game. Players are identified by distinct integers from $$$1$$$ to $$$P$$$, according to the order they take turns. For $$${i}={1}, {2}, \ldots, {P}$$$, the $$$i$$$-th of the next $$$P$$$ lines contains two integers $$$A_i$$$ and $$$B_i$$$ ($$$-10^9 \leq A_i, B_i \leq 10^9$$$), indicating that the line in the card picked by player $$$i$$$ is $$$y = A_i x + B_i$$$.

Output

Output $$$P$$$ lines. For $$${i}={1}, {2}, \ldots, {P}$$$, the $$$i$$$-th line must contain an integer $$$K_i$$$ indicating the number of tokens that player $$$i$$$ receives, followed by $$$K_i$$$ integers identifying those tokens in ascending order.

Examples
Input
5
0 0
5 0
4 3
2 4
2 -1
3
-1 5
0 2
1 1
Output
2 1 5
1 2
1 3
Input
2
0 0
1 1
2
0 1
0 1
Output
1 1
0