Knight Tournament Earnings

Welcome to the Knight Tournament Earnings problem!

There are N knights and each knight has a unique identifier from 1 to N. The knights have organized themselves into different knight teams: the i-th knight belongs to team (a_i).

After the teams are formed, the tournament lasts for M days. On each day, two distinct teams, x and y, are chosen. Every knight in team x will face every knight in team y exactly once. When a knight with identifier (i) from team x confronts a knight with identifier (j) from team y, if you bet on the match successfully, you earn your wagered capital back plus an additional profit of (i \times j) source stone ingots. Note that every bet requires you to risk your entire capital; however, for the purpose of this problem, simply compute the total extra earnings from all the match-ups on that day.

Your task is to determine the total amount of source stone ingots earned on each day. More formally, for each day, output the sum (\sum (i \times j)) over every pair where (i) is a knight from team x and (j) is a knight from team y.

Note: It is guaranteed that the answer fits within a 64-bit signed integer.

inputFormat

The first line contains two integers, N and M.

The second line contains N integers: (a_1, a_2, \ldots, a_N), where (a_i) is the team number of the i-th knight.

Each of the next M lines contains two distinct integers, x and y, indicating that on that day, team x and team y will compete.

outputFormat

Output M lines. For each day, print a single integer representing the total source stone ingots earned on that day, which is the sum over all pairs (i \times j) with (i) from team x and (j) from team y.

sample

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

8
16
8