28251번 - 나도리합

문제

나도리는 자신을 터트린 나도리팡의 제작자에게 복수하기 위해 만반의 준비를 해왔다. 각 나도리 $i$는 크기 $s_i$를 가지며, 정확히 하나의 나도리 그룹에 속한다. 두 나도리 그룹이 융합하면 둘에 속한 모든 나도리로만 이루어진 새 나도리 그룹 하나로 대체된다. 나도리 그룹의 전투력은 그룹에 속한 서로 다른 두 나도리의 크기를 곱한 것을 모두 합한 값이다.

아래는 나도리 그룹 $G$의 전투력을 수식으로 표현한 것이다.

$$\sum_{i, j\in G,\ i < j}s_i\cdot s_j$$

나도리들의 복수를 도와주기 위하여 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

• $a ,円 b$ : 나도리 $a$가 속한 나도리 그룹과 나도리 $b$가 속한 나도리 그룹을 융합한 뒤, 나도리 $a$와 나도리 $b$가 속한 나도리 그룹의 전투력을 출력한다. (단, 같은 나도리 그룹끼리는 융합하여도 변화가 없다)

입력

첫째 줄에 나도리의 수 $N (2 \leq N \leq 200,000円),ドル 쿼리의 수 $Q (1 \leq Q \leq 200,000円)$가 공백으로 구분되어 주어진다.

둘째 줄에 각 나도리의 크기를 나타내는 $N$개의 정수 $s_1, s_2, \dots, s_N$이 공백으로 구분되어 주어진다. $(0 \leq s_i \leq 2,000円)$

셋째 줄부터 $Q$개 줄에 걸쳐 쿼리를 나타내는 정수 $a, b$가 공백으로 구분되어 주어진다. $(1 \leq a, b \leq N; a \neq b)$

출력

$Q$개의 줄에 걸쳐 쿼리의 결괏값을 출력한다.

제한

힌트