나무에 내리는 햇빛

나무를 바로 위에서 내려다보자. 가지를 간선으로, 가지가 갈라지거나 끝나는 지점을 정점으로 보면 위에서 본 모습은 평면에 그려진 그래프가 된다. 그림에서 간선끼리 교차할 수는 있지만 그래프 자체는 트리다. 즉 연결되어 있고 사이클이 없으며, 2차원 좌표가 하나씩 붙은 정점 $n$개와 간선 $n - 1$개로 이루어진다.

질의는 네 수 $u$, $v$, $x$, $y$로 주어진다. $u$와 $v$는 정점 두 개이고, 벡터 $(x, y)$는 햇빛이 나아가는 방향이다. 햇빛은 광선 하나가 아니라 무한히 먼 곳에서 출발해 $(x, y)$ 방향으로 나아가는 평행한 광선의 다발이다. 아래 그림은 $(x, y) = (2, 1)$인 경우로, 빛은 왼쪽 아래에서 들어오고 모든 광선은 벡터 $(2, 1)$과 평행하다.

빛이 먼저 닿는 정점일수록 더 따뜻하다. 광선이 $(x, y)$ 방향으로 나아가므로, 좌표가 $(p_x, p_y)$인 정점은 $x p_x + y p_y$가 작을수록 빛을 먼저 받는다. 개미가 $u$에서 $v$까지 트리의 유일한 최단 경로를 따라 이동한다. 이 경로 위의 정점 가운데 햇빛이 가장 먼저 닿는 정점, 즉 $x p_x + y p_y$가 최소인 정점을 모두 구하라.

두 번째 그림은 정점 14개로 이루어진 트리다. $u = 14$, $v = 4$, $x = 1$, $y = 0$이면 경로는 14, 11, 1, 3, 4이고 빛이 왼쪽에서 들어오므로 정점 3과 11에 햇빛이 가장 먼저 닿는다. $u = 13$, $v = 9$, $x = 1$, $y = -1$이면 경로는 13, 11, 1, 6, 9이고 빛이 왼쪽 위에서 들어오므로 정점 1, 6, 11에 햇빛이 가장 먼저 닿는다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($T \le 10$). 각 테스트 케이스의 첫 줄에는 정점의 수 $n$이 주어진다 ($1 \le n \le 10^5$). 다음 $n$개 줄에는 정점의 좌표가 한 줄에 하나씩 주어지며, 그중 $i$번째 줄이 정점 $i$의 좌표다 ($|x|, |y| \le 10^5$). 좌표가 같은 정점이 여러 개 있을 수 있다. 다음 $n - 1$개 줄에는 간선이 잇는 두 정점의 번호가 주어지고, 번호는 1 이상 $n$ 이하다. 입력은 항상 올바른 트리다. 다음 줄에는 질의의 수 $Q$가 주어진다 ($1 \le Q \le 1.6 \times 10^5$). 다음 $Q$개 줄에는 질의가 $u$ $v$ $x$ $y$ 형태로 하나씩 주어진다 ($1 \le u, v \le n$, $|x|, |y| \le 10^5$). 벡터 $(x, y)$는 영벡터가 아니고, $u$와 $v$는 같을 수 있다. 모든 테스트 케이스가 최대 크기는 아니지만, 정점 수와 질의 수가 가장 큰 케이스가 적어도 하나 있다.

각 테스트 케이스마다 먼저 Case k:를 한 줄에 출력한다. $k$는 1부터 세는 테스트 케이스 번호다. 그 뒤로 질의마다 한 줄씩, 햇빛이 가장 먼저 닿는 정점의 번호를 오름차순으로 정렬해 공백 하나로 구분해 출력한다. 줄의 처음과 끝에는 공백을 넣지 않는다. 입력 전체에서 출력하는 번호는 최대 $3 \times 10^5$개다.