P10523 [XJTUPC 2024] Everyone's ALL IN

Ladies and gentlemen. Good morning, good afternoon, and good evening. Welcome to the “So Good It Can’t Get Any Better! Terra Master Investment Class”. I am your Teacher Kan. Not 10000, not 5000, only 999 Originium Ingots. One-on-one guidance, hands-on teaching, from beginner to expert, so that you can: — **Win every pick, hit every bet**, quickly achieve financial freedom and become very rich! Today’s location is — the **Kazimierz Knight Tournament**. This tournament is a bit different. First, $N$ knights will form knight orders on their own, where knight $i$ will join knight order $a_i$. Then, over the next $M$ days, each day two different knight orders $x$ and $y$ will be specified. After that, every member in knight order $x$ will duel once with every member in knight order $y$. For each duel, we will place a bet. If the two knights’ indices are $a$ and $b$, then if your bet succeeds, you will get back your principal plus $a\times b$ Originium Ingots. Of course, for each bet you must stake **all your principal**! So, over the next $M$ days, under my guidance, how many Originium Ingots can you earn each day? **The data guarantees that the answer does not exceed the range of a 64-bit signed integer.** **Gambling is risky. Invest with caution!** 

The first line contains two positive integers $N$ ($1\le N \le 2\times 10^5$) and $M$ ($1\le M \le 2\times 10^5$), separated by spaces. The next line contains $N$ positive integers $a_i$ ($1\le a_i \le 1\times 10^6$) separated by spaces, meaning that the knight with index $i$ belongs to the knight order with index $a_i$. The next $M$ lines each contain two positive integers $x_i,y_i$ separated by spaces ($x_i \neq y_i$), and it is guaranteed that $x_i,y_i$ appear among $a_1 \sim a_n$.

Output $M$ lines. Each line contains one positive integer. The $i$-th line represents the maximum profit obtainable on day $i$. **The data guarantees that the answer does not exceed the range of a 64-bit signed integer.**

The members of knight order $1$ are $\{1,2,9\}$, the members of knight order $2$ are $\{3,4,8\}$, and the members of knight order $3$ are $\{5,6,7\}$. On the first day, knight order $1$ and knight order $2$ compete. The profit obtained is: $1\times 3+1\times 4+1\times 8+2\times 3+2\times 4+2\times 8+9\times 3+9\times 4+9\times 8=180$. On the second day, knight order $2$ and knight order $3$ compete. The profit obtained is: $3\times 5+3\times 6+3\times 7+4\times 5+4\times 6+4\times 7+8\times 5+8\times 6+8\times 7=270$. On the third day, knight order $1$ and knight order $3$ compete. The profit obtained is: $1\times 5+1\times 6+1\times 7+2\times 5+2\times 6+2\times 7+9\times 5+9\times 6+9\times 7=216$. Translated by ChatGPT 5