Hide

Problem N
Dragon Maid

Being new to the human world, Tohru realises romantic relationships are complicated, involving the reciprocation of the other party. Not to be deterred, Tohru decides to find a way to win over her master, Kobayashi-san’s heart. With Valentine’s day coming up, its Tohru’s best opportunity to buy a gift for Kobayashi.

Having built a reputation in Oborozuka Shopping District for nabbing a thief, Tohru visits her favourite shop. The shop has $N$ unique items in a line. Tohru assigns two values for each item:

  • $P_{i}$, the value she perceives the item to be at, and

  • $V_{i}$, the estimated value that Kobayashi values the item at.

Being a poor dragon, Tohru needs to save money and cannot buy every item. Tohru will do some mental gymnastics to narrow her search for the item she wants to buy. She is currently processing $Q$ queries in her head. For each query:

  1. Tohru first thinks of two integers: $X$ and $K$.

  2. She then starts filtering the items whose $V_{i} \leq X$.

  3. After that, she ranks the filtered items:

    1. Item $i$ is better than item $j$ if $P_ i > P_ j$.

    2. If $P_ i = P_ j$, then the smaller index between $i$ and $j$ is the better one.

  4. Finally, she wants to know the indices of the best $K$ items.

Being a battle-hardened dragon since birth, Tohru is not very good at academics and needs your help to calculate the answer for every query.

Input

The first line contains an integer, $N~ (1 \le N \le 200\, 000)$. The next $N$ lines contain the items, each on one line. Each item is given in a form of two integers: $P_{i}$ and $V_{i}$ ($1 \leq P_{i}, V_{i} \leq 10^{9}$).

The next line contains an integer $Q~ (1 \le Q \le 200\, 000)$. The next $Q$ lines contain the queries, each on one line. Each query is given in a form of two integers: $X$ and $K$ ($0 \leq X \leq 10^{9},~ 1 \leq K \leq 10$) as defined above.

Output

For each query, print the best $K$ indices in any order on a single line, separated by a space. If there are less than $K$ valid indices for a query, then print all of those only valid indices. If there is no valid indices for a query, then print $-1$ instead. The answers to different queries must be outputted on separate lines.

Subtasks

  1. ($6$ Points): $N \leq 100, Q \leq 100$ and $P_{i} = V_{i} = i$, $\forall i \in [1..N]$.

  2. ($18$ Points): $N \leq 100, Q \leq 100$.

  3. ($11$ Points): $P_{i} = V_{i}$, $\forall i \in [1..N]$.

  4. ($20$ Points): At most $5$ distinct values of $V_{i}$ and $K = 1$ for every query.

  5. ($7$ Points): At most $5$ distinct values of $V_{i}$ and $Q \leq 25\, 000$.

  6. ($27$ Points): $K = 1$ for every query.

  7. ($11$ Points): No additional constraint.

Explanation of Sample Input $2$

  1. For the first query, all items have their respective $V_{i} \leq 4$. Since only the best $1$ item needs to be printed and item $1$ has the highest $P_{i}$, thus the answer is $1$.

  2. For the second query, only items $2$ and $3$ have their $V_{i} \leq 3$. Since we break ties by indices, we print item $2$.

Sample Input 1 Sample Output 1
5
1 1
2 2
3 3
4 4
5 5
3
3 3
5 5
4 4
1 2 3
1 2 3 4 5
1 2 3 4
Sample Input 2 Sample Output 2
3
2 4
1 2
1 3
2
4 1
3 1
1
2
Sample Input 3 Sample Output 3
5
1 2
4 4
2 3
5 6
3 4
7
5 3
4 3
3 2
6 4
5 3
1 4
6 10
2 3 5
2 3 5
1 3
2 3 4 5
5 3 2
-1
1 2 3 4 5

Please log in to submit a solution to this problem

Log in