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

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

한 길드에 속한 모험가들의 전투력이 \(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

첫 번째 명령으로 전투력이 \(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\)

First line \(N\) and \(Q\); second line \(N\) powers \(A_i\); then \(Q\) lines each with \(a\), \(b\) (\(1 \le N, Q \le 10^5\), \(1 \le A_i \le 1000\), \(a \ne b\)).

Print the resulting synergy after each command, one per line.

riseoj 작성

출처 Online Judge > GoldOJ