H. AI Thoughts

Time limit: 1.5s Memory limit: 256MB Input: Output:

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 nn neurons placed. We know for each neuron its position in the grid and its color, given as a tuple (x,y,col)(x, y, col). An AI Thought is described by:

  • The length of the neural sequence mm, meaning that our thought is created by a list of mm neurons.
  • The colors we want to use for our list of neurons, col1,col2, colmcol_1, col_2, \dots \ col_m. This means that the ithi^{th} neuron in our thought list should have the color colicol_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(i1,i2)+manh(i2,i3)++manh(im1,im)manh(i_1, i_2) + manh(i_2, i_3) + \dots + manh(i_{m-1}, i_m), where manh(i,j)manh(i, j) is the Manhattan distance between points (neurons) ii and jj in the grid(xixj+yiyj|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 TT thoughts the maximum possible amount of time for generating each thought.

Input data

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

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

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

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

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

Output data

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



1 1 3
-1 4 2
3 2 4
4 1 1
-2 -3 4
-1 2 1
2 2 3
3 0 2
1 2 1 2 4
3 1 2




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.

Log in or sign up to be able to send submissions!