Minimax Tree

Minimax 알고리즘은 체스, 바둑, 틱택토처럼 두 사람이 번갈아 두는 게임에서 쓰인다. 이 알고리즘에 쓰는 Minimax 트리는 상대방이 최선의 수를 둘 때 나에게 미치는 영향이 가장 작도록 만든 게임 트리이다. 기준이 되는 사람(MAX)은 자식 노드 중 값이 가장 큰 것을 고르고, 상대(MIN)는 값이 가장 작은 것을 고른다. 이렇게 양쪽의 최선의 전략을 찾는 방법이다.

Minimax 트리는 다음과 같이 구성된다.

• 트리에서 리프 노드의 값들은 모두 계산되어 있다.
• 게임에서 선 플레이어는 MAX player로 루트 노드부터 시작한다.
• 루트 노드부터 자식 노드로 내려갈 때마다 MAX player와 MIN player가 번갈아 바뀐다.
• 리프 노드가 아니면서 MAX player인 노드의 값은 자식 노드의 값들 중 최댓값으로 계산한다.
• 리프 노드가 아니면서 MIN player인 노드의 값은 자식 노드의 값들 중 최솟값으로 계산한다.

수민이는 친구와 게임을 하기로 했다. 게임에서 이기면 받은 점수만큼 상품을 받는다. 수민이는 상품을 최대한 얻으려고 Minimax 트리를 그려 최적의 전략을 찾아 두었다. 그런데 친구가 이를 눈치채고 트리의 숫자 일부에 색칠을 해서 수민이를 방해하기 시작했다. 다행히 친구는 리프 노드의 숫자는 건드리지 않았으므로 리프 노드의 값은 알 수 있다. 트리를 완성하고, 값을 구해야 하는 노드가 주어지면 그 노드의 값을 출력하자.

첫째 줄에 트리 정점의 수 $N$과 루트의 번호 $R$이 공백으로 구분되어 주어진다. ($2 \leq N \leq 10^5$, $1 \leq R \leq N$)

둘째 줄부터 $N$번째 줄까지 $N - 1$줄에 걸쳐 트리 간선의 양 끝 점 $u, v$가 공백으로 구분되어 주어진다. ($1 \leq u$, $v \leq N$, $u \ne v$)

이어 리프 노드의 개수 $L$이 주어진다. ($1 \leq L \leq N$이며 입력으로 주어진 트리의 리프 노드의 개수와 $L$은 항상 같다)

다음 $L$줄에 걸쳐 리프 노드의 번호 $k\_i$와 노드의 값 $t\_i$가 공백으로 구분되어 주어진다. ($1 \leq k\_i \leq N$, $0 \leq t\_i \leq 10^9$, $1 \leq i \leq L$)

이어 값을 구해야 할 노드의 개수 $Q$가 주어진다. ($1 \leq Q \leq 10^5$)

다음 $Q$줄에 걸쳐 값을 구해야 할 노드의 번호 $q\_i$가 주어진다. ($1 \leq q\_i \leq N$, $1 \leq i \leq Q$)

$Q$줄에 걸쳐 각 노드의 값을 한 줄에 하나씩 출력한다.