나도리합

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

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

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

• $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$개 줄에 걸쳐 각 쿼리의 결괏값을 출력한다.