각 모험가는 전투력을 하나씩 가지고 있다.

처음에는 모든 모험가가 서로 다른 길드에 속해 있다. 이후 두 모험가가 속한 길드를 합치는 명령이 주어진다.

한 길드에 속한 모험가들의 전투력이 \(x_1, x_2, \ldots, x_k\)라고 하자. 이 길드의 시너지 값은 서로 다른 두 모험가를 고르는 모든 방법에 대해 전투력의 곱을 더한 값이다.

즉, 시너지 값은 다음과 같다.

\(\sum_{1 \le i < j \le k} x_i x_j\)

각 명령을 처리한 뒤, 두 모험가가 속하게 된 길드의 시너지 값을 출력하시오.

이미 같은 길드에 속한 두 모험가가 주어지면 길드는 변하지 않으며, 현재 그 길드의 시너지 값을 그대로 출력한다.

입력

첫째 줄에 모험가의 수 \(N\)과 명령의 수 \(Q\)가 공백으로 구분되어 주어진다.

둘째 줄에 각 모험가의 전투력 \(A_1, A_2, \ldots, A_N\)이 공백으로 구분되어 주어진다.

다음 \(Q\)개의 줄에는 길드를 합칠 두 모험가 \(a\), \(b\)가 공백으로 구분되어 주어진다.

출력

각 명령을 처리한 뒤, 두 모험가가 속하게 된 길드의 시너지 값을 한 줄에 하나씩 출력한다.

제한 사항

• \(1 \le N \le 100,000\)
• \(1 \le Q \le 100,000\)
• \(1 \le A_i \le 1,000\)
• \(1 \le a, b \le N\)
• \(a \ne b\)
• 출력해야 하는 모든 시너지 값은 signed 64-bit 정수 범위를 넘지 않는다.

예제 입력 1

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

예제 출력 1

8
15
71

예제 설명 1

첫 번째 명령으로 전투력이 \(2\), \(4\)인 모험가가 같은 길드가 된다.

이 길드의 시너지 값은 \(2 \times 4 = 8\)이다.

두 번째 명령으로 전투력이 \(3\), \(5\)인 모험가가 같은 길드가 된다.

이 길드의 시너지 값은 \(3 \times 5 = 15\)이다.

세 번째 명령으로 앞의 두 길드가 합쳐진다. 새 길드에 속한 모험가들의 전투력은 \(2\), \(4\), \(3\), \(5\)이다.

따라서 시너지 값은 다음과 같다.

\(2 \times 4 + 2 \times 3 + 2 \times 5 + 4 \times 3 + 4 \times 5 + 3 \times 5 = 71\)

예제 입력 2

4 4
10 20 30 40
1 2
1 2
3 4
2 4

예제 출력 2

200
200
1200
3500