eolymp
bolt
Try our new interface for solving problems
Problems

Invasion

Invasion

Time limit 2 seconds
Memory limit 64 MiB

It has been hundreds of centuries since our first space flight and the farthest settlements humanity has founded are not strange new worlds, but a few rusting space stations. We never listened to those aware of our unpreparedness and the passage of time made the improbable a certainty: Earth has been conquered. Our planet's states will be divided among two alien empires as soon as an agreement on their shares is made.

Today's Earth is a sphere, whose surface is divided into states. Every state is an area with connected borders and connected interior, whose borders do not self-intersect. No more than three borders can meet at one point. After our world is divided, each empire's territory must also be an area with connected borders and connected interior, whose borders do not self-intersect.

The aliens are facing the following problem: given a division of our planet's surface, calculate the absolute value of the difference between numbers of states in each empire's territory. In order to gain their trust, human leaders have decided to help them.

Input data

The first line of input contains a single integer t, the number of test cases. t test cases follow.

A test case is a description of the world map, followed by multiple queries made by the aliens.

Let a special point be a point where three borders meet. The first line of the description of the world map contains an integer n (4 n 100 000), after which there are n lines each of which contains numbers x_i, y_i, z_i, s_{i,1}, s_{i,2}, s_{i,3} (1 i n) that describe the special points. The real numbers x_i, y_i, z_i are coordinates of the i-th special point. All special points belong to the surface of the same sphere whose center is located in (0, 0, 0) and whose radius is r (1r1000). The coordinates are given with absolute error of 10^{-6}. You can assume that the accuracy of the input is enough for the answer to be unambiguous. The integer numbers s_{i,1}, s_{i,2}, s_{i,3} denote the special points that are connected to the i-th special point by a border. The border is always the minor arc of a great circle. No border connects two diametrally opposite points.

After the world map, the description of the queries follows. The first line of the description contains a single integer m (1 m 200 000) denoting the number of queries. Each of the next m lines is a description of a division of Earth's surface between two empires. The description of the i-th division begins with the integer k_i, followed by k_{i }identifiers of special points that, in that order, form the border of the division. No other special point is at the border of the division. The border satisfies the conditions mentioned earlier.

Output data

For each test case, output m numbers on a separate line. The i-th number should be the absolute value of the difference between numbers of states in each empire's territory according to the i-th division.

Examples

Input example #1
1
4
1 1 1 2 3 4
-1 1 1 1 3 4
1 -1 1 1 2 4
1 1 -1 1 2 3
2
3 1 2 3
4 1 2 3 4
Output example #1
2 0
Source 2013 Petrozavodsk Winter Training Camp, Jagiellonian University Contest, January 25, Problem I