트리 읽기

$N$ 개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점에는 $1$ 이상 $9$ 이하인 숫자가 하나 쓰여 있다. 트리의 각 정점은 $1$번부터 $N$번까지 번호가 매겨져 있다. 아래 그림이 위 조건을 만족하는 트리의 예이다. 각 정점 안에 있는 수는 정점의 번호, 정점 위의 숫자는 정점에 쓰인 숫자이다.

$M$ 명의 사람이 있다. 각 사람은 $1$번부터 $M$번까지 번호가 매겨져 있다. 각 사람들은 트리에서 출발 정점과 도착 정점을 선택한다. 출발 정점에서 도착 정점을 잇는 경로에 있는 정점들에 쓰인 숫자를 차례대로 읽으면 수를 만들 수 있다. 예를 들어, $1$번 정점에서 출발하여 $3$번 정점으로 도착하는 경로는 차례대로 $1$번 정점, $2$번 정점, $3$번 정점을 방문하게 되고, $2$, $1$, $2$를 차례로 읽어 $212$가 만들어진다.

$M$ 명의 사람들이 만드는 $M$ 개의 수를 오름차순으로 정렬하여, 사람들에게 등수를 매기려고 한다. 만약 만든 수가 동일한 경우, 번호가 낮은 사람이 앞에 온다.

트리의 정보, 각 사람이 선택한 출발 정점과 도착 정점이 주어졌을 때, 사람의 번호를 등수 순서대로 출력하는 프로그램을 작성하라.

입력 형식

첫 줄에 정점의 수를 나타내는 정수 $N$과 사람의 수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 150\,000;$ $2 \le M \le 150\,000$)

그다음 줄에 $N$ 개의 숫자 $D_1, D_2, \cdots D_N$가 공백으로 구분되어 주어진다. 이는 $i$번 정점에 적혀있는 숫자가 $D_i$임을 의미한다. ($1 \le D_i \le 9$)

이어지는 $N-1$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 간선의 정보를 나타내는 두 정수 $U_i$와 $V_i$가 공백으로 구분되어 주어진다. 이는 $U_i$번 정점과 $V_i$번 정점을 잇는 간선을 의미한다. ($1 \le U_i, V_i \le N$)

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$번 사람이 선택한 출발 정점의 번호 $S_i$와 도착 정점의 번호 $E_i$가 공백으로 구분되어 주어진다. ($1 \le S_i, E_i \le N;$ $S_i \ne E_i$)

출력 형식

$M$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에 $i$ 번째 순위를 기록한 사람의 번호를 출력한다.

예제 1

6 6
2 1 2 3 1 2
1 2
2 3
2 4
4 5
4 6
1 3
3 1
1 6
5 1
2 4
4 5

5
6
1
2
4
3

예제 2

5 3
1 5 7 3 2
1 2
2 3
3 4
4 5
1 5
3 5
2 4

3
2
1

예제 설명

입력 예제 1에서, 각 사람이 만든 수는 $212$, $212$, $2132$, $1312$, $13$, $31$이며, 각 사람들의 등수는 차례로 $3$, $4$, $6$, $5$, $1$, $2$이 된다. 1등은 $5$번, 2등은 $6$번, 3등은 $1$번, 4등은 $2$번, 5등은 $4$번, 6등은 $3$번이 되므로 출력 결과는 $5$ $6$ $1$ $2$ $4$ $3$이 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설