Sunlight on a Tree

Look down on a tree from directly above. Each branch is an edge and each point where branches meet or end is a node, so the top view is a graph drawn on the plane. Edges of the drawing may cross, but the graph itself is a tree: it is connected and has no cycle, and its $n$ nodes, each placed at a 2D coordinate, are joined by $n - 1$ edges.

A query gives four numbers $u$, $v$, $x$, $y$. Here $u$ and $v$ are two nodes, and the vector $(x, y)$ is the direction the sunlight travels. The sunlight is not a single ray. It is a bundle of parallel rays that comes from infinitely far away and moves along $(x, y)$. The figure below draws $(x, y) = (2, 1)$: the light arrives from the lower left and every ray is parallel to $(2, 1)$.

A node is warmer when the light reaches it earlier. The rays travel along $(x, y)$, so the light reaches a node at $(p_x, p_y)$ earlier when $x p_x + y p_y$ is smaller. An ant walks from $u$ to $v$ along the unique shortest path of the tree. Report every node on that path that the sunlight reaches first, that is, every node of the path whose value of $x p_x + y p_y$ is minimum.

The second figure shows a tree with 14 nodes. For $u = 14$, $v = 4$, $x = 1$, $y = 0$ the path is 14, 11, 1, 3, 4, the light comes from the left, and the sunlight reaches nodes 3 and 11 first. For $u = 13$, $v = 9$, $x = 1$, $y = -1$ the path is 13, 11, 1, 6, 9, the light comes from the upper left, and the sunlight reaches nodes 1, 6 and 11 first.

The first line contains the number of test cases $T$ ($T \le 10$). Each test case starts with a line holding the number of nodes $n$ ($1 \le n \le 10^5$). The next $n$ lines hold the node coordinates, one node per line, and the $i$-th of those lines gives the coordinates of node $i$ ($|x|, |y| \le 10^5$). Several nodes may sit at the same coordinates. Each of the next $n - 1$ lines holds the ids of the two nodes that an edge connects, and an id is between 1 and $n$. The input is always a valid tree. The next line holds the number of queries $Q$ ($1 \le Q \le 1.6 \times 10^5$). Each of the next $Q$ lines holds one query in the form $u$ $v$ $x$ $y$ ($1 \le u, v \le n$, $|x|, |y| \le 10^5$). The vector $(x, y)$ is never the zero vector, and $u$ and $v$ may be the same node. Not every test case is a worst case, but at least one of them uses the largest number of nodes and queries.

For each test case print a line Case k:, where $k$ is the number of the test case counting from 1. Then print one line per query holding the ids of the nodes that the sunlight reaches first, sorted in increasing order and separated by single spaces. Do not put a space at the beginning or the end of a line. Over the whole input your program prints at most $3 \times 10^5$ ids.