RCPC Simulare 2023 day 2 | H. AI Thoughts

As you all know, AI use is on the rise. As our friend Gigel dislikes this, he came up with a plan of sabotaging the growth of AI.

An AI brain works in intricate ways. First lets consider an infinite grid where there are $n$ neurons placed. We know for each neuron its position in the grid and its color, given as a tuple $(x, y, col)$. An AI Thought is described by:

• The length of the neural sequence $m$, meaning that our thought is created by a list of $m$ neurons.
• The colors we want to use for our list of neurons, $col_1, col_2, \dots \ col_m$. This means that the $i^{th}$ neuron in our thought list should have the color $col_i$. As an important observation, we are allowed to use the same neuron multiple times in our list.
• The time we need to generate this thought is $manh(i_1, i_2) + manh(i_2, i_3) + \dots + manh(i_{m-1}, i_m)$, where $manh(i, j)$ is the Manhattan distance between points (neurons) $i$ and $j$ in the grid($|x_i - x_j| + |y_i - y_j|$).

Now, depending on how we choose the neurons, the time needed for generating a thought can differ. As Gigel hates AI, he wants to prove the world how inefficient it is, so he asks for your help. In order to do this, you need to compute for $T$ thoughts the maximum possible amount of time for generating each thought.

Input data

The first line of the input contains $n$, the number of neurons ($1 \le n \le 2 \cdot 10^5$).

The next $n$ lines of the input contain the neurons we can use for our thoughts ($-10^9 \le x_i, y_i \le 10^9$), ($1 \le col \le 2 \cdot 10^5$).

The next line contains $t$, the number of thoughts we need to analyze ($1 \le t \le 2 \cdot 10^5$).

The next $t$ lines contain $m_i$, the number of points in the thought ($1 \le m_i \le 2 \cdot 10^5)$ and then $m_i$ inteegers representing the colors we need to use for the neurons in this thought ($1 \le col_i \le 2 \cdot 10^5)$.

It is guaranteed that the sum of values $m_i$ is at most $5 \cdot 10^5$ and each color $col_i$ used is present in at least one neuron from the set of neurons.

Output data

The output will contain $t$ lines, on each line we have the answer for the $i^{th}$ question.

Example

stdin

8
1 1 3
-1 4 2
3 2 4
4 1 1
-2 -3 4
-1 2 1
2 2 3
3 0 2
2
5
1 2 1 2 4
3
3 1 2

stdout

32
11

Explanation

For the first thought, we can use the fourth, the second, the fourth, the second and the fifth neuron, in this order.

For the second thought, we can use the first, the fourth and the second neuron, in this order.