25361번 - Global Warming 스페셜 저지다국어

You are developing a new computer game. Let's consider an island in the middle of the ocean in a three-dimensional space with $z$-axis pointing upwards. The surface of the ocean is a horizontal plane with $z = 0$. The island is a polyhedron of a special form.

You are given $n$ points $(x_i, y_i, z_i)$; there are some edges between them. If we look at the island from above or if we discard $z$ coordinate of each point, points and edges form a planar connected graph. Every face of this planar graph, except the external one, is a nondegenerate triangle. Every edge of the graph belongs to at least one internal face. All points that lie on the edge of the external face of the graph have $z$ coordinates equal to zero. Other points may have arbitrary non-negative $z$ coordinates. Every face of the planar graph corresponds to the face of the polyhedron with the same vertices.

Due to global warming, the level of the ocean is increasing and floods the island. Your task is to compute various global warming scenarios for the game.

In each scenario, the level of the ocean increased to the height $h$, so that the surface of the ocean is a plane $z = h$. Parts of the island that are below or at the height $h$ are now flooded, even though some parts may be not reachable from the ocean by water (see the illustration for the second example). In a scenario, a player is standing in $p$-th point. You shall compute the area of the surface of the part of the island where the player is standing, or determine that the player is standing at or below the water level and has drowned.

Formally, we say that two points on the surface of the island belong to the same part if a player can move between them walking by the surface of the island staying strictly higher than ocean level. Note that you should find the area of the surface of the island itself, not the area of its projection on a horizontal plane.

The first line contains a single integer $n$ --- the number of points ($1 \le n \le 10^5$).

Each of the next $n$ lines contains three integers $x_i$, $y_i$, and $z_i$ --- the coordinates of $i$-th point ($-10^6 \le x_i, y_i \le 10^6$; $0 \le z_i \le 10^6$).

The next line contains a single integer $m$ --- the number of internal faces of the planar graph ($1 \le m \le 10^5$). They are also the faces of the island's polyhedron.

Each of the next $m$ lines contains three integers $a_i$, $b_i$, and $c_i$ --- the indices of three points that are vertices of $i$-th internal face ($1 \le a_i, b_i, c_i \le n$).

It is guaranteed that if $z$ coordinate is discarded, then the resulting graph is a connected and planar graph. All its faces, except the external one, are nondegenerate triangles. All points that lie on the edge of the external face of the planar graph have $z$ coordinate equal to zero.

The next line contains an integer $q$ --- the number of global warming scenarios to compute ($1 \le q \le 10^5$).

Each of the next $q$ lines contains two integers $h_i$ and $p_i$ --- the level of the ocean and the index of the point where the player is standing respectively ($0 \le h_i \le 10^6$; $1 \le p_i \le n$).

For every scenario output a single real number --- the area of the surface of part of the island where the player is standing. If the player's position is flooded by water, output $-1$ instead.

The answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.