배경

환광유영(幻光留影) 장치는 10주년을 기념하기 위해 주회장에 설치된 대형 인터랙티브 예술 작품입니다. 이 장치는 여러 개의 부유하는 영상 노드로 구성되어 있으며, 광속으로 연결되어 나무 형태를 이룹니다. 각 노드에는 서로 다른 색상의 광영 필터가 설정되어 있습니다. 제어 콘솔에서 매개변수를 조절하면 시스템은 특정 번호 구간 내의 광속만 일시적으로 활성화하며, 이로 인해 원래 연결되어 있던 전체 네트워크가 여러 개의 독립적인 연결 성분으로 분리됩니다.

흥미로운 점은 동일한 연결 성분 내에서 같은 색상의 필터를 가진 노드들 사이에 광학적 간섭이 발생한다는 것입니다. 특정 색상의 필터가 해당 연결 성분 내에서 짝수 번 등장하면 그 빛은 서로 상쇄되어 보이지 않게 되며, 홀수 번 등장하면 선명하게 보이는 색상으로 합쳐집니다.

빛과 그림자의 분리와 재결합은 매우 매혹적입니다. 당신은 이 구조적 변화에 깊은 관심을 가지게 되었습니다. 이러한 부분적 활성화가 일어날 때마다, 분리된 모든 연결 성분 각각에 포함된 가시적 필터(즉, 등장 횟수가 홀수인 필터 색상) 종류 수의 총합은 얼마일까요?

문제 설명

환광유영 장치는 $n$개의 노드를 포함하는 트리로 추상화할 수 있으며, 각 노드는 영상 노드를 나타내고 노드 $i$ ($1 \le i \le n$)의 필터 색상은 $c_i$입니다. 노드를 연결하는 광속은 총 $n-1$개이며, 각각 $1$부터 $n-1$까지 번호가 매겨져 있습니다.

규칙을 탐색하는 과정에서 $m$번의 동적 효과 테스트 데이터를 기록했습니다. 각 테스트마다 광속 번호 구간 $[l, r]$을 지정합니다. 이때 해당 구간 내에 포함된 번호의 광속만 활성화하고(구간에 포함되지 않은 다른 광속은 차단), 원래 연결되어 있던 전체 네트워크가 여러 개의 독립적인 연결 성분으로 분리된다고 가정합니다.

각 테스트마다 다음 값을 계산해야 합니다: 모든 연결 성분 각각에 포함된 가시적 필터(즉, 등장 횟수가 홀수인 필터 색상) 종류 수의 총합.

입력

입력의 첫 번째 줄에는 두 개의 양의 정수 $n, m$ ($1 \le n \le 3 \times 10^5, 1 \le m \le 10^6$)이 주어지며, 각각 영상 노드의 수와 테스트 횟수를 나타냅니다.

입력의 두 번째 줄에는 $n$개의 양의 정수 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$)이 주어지며, 각각 각 영상 노드의 필터 색상을 나타냅니다.

이어지는 $n-1$개의 줄 중 $i$번째 줄 ($1 \le i \le n-1$)에는 두 개의 양의 정수 $u_i, v_i$ ($1 \le u_i, v_i \le n$)가 주어지며, 번호가 $i$인 광속이 연결하는 두 노드를 나타냅니다.

이어지는 $m$개의 줄에는 각각 두 개의 양의 정수 $l, r$ ($1 \le l \le r \le n-1$)이 주어지며, 한 번의 테스트에 대한 광속 번호 구간을 나타냅니다.

출력

$m$개의 줄을 출력하십시오. 각 줄에는 해당 테스트에서 모든 독립적인 연결 성분이 각각 포함하는 가시적 필터 종류 수의 총합을 나타내는 비음의 정수를 출력해야 합니다.

예제

입력 1

12 13
2 4 1 2 3 4 2 4 3 3 3 6
3 5
9 1
5 11
4 9
1 12
2 1
10 8
11 10
8 4
6 11
7 6
1 3
2 2
6 6
9 11
6 11
1 4
8 10
1 11
5 10
4 7
1 10
6 8
11 11

출력 1

10
12
12
12
6
8
10
4
8
12
4
10
12