Galactic Railway

A galaxy contains many planets. Technological progress has made it possible for every planet in a galaxy to travel to any other.

Today, a galactic railway connecting our galaxy to another one 80,000 light-years away finally opens.

Residents of every planet in the galaxy are excited at the prospect of traveling to more planets once the galactic railway opens.

The space railway authority G-Express has announced its future galactic railway plans.

Since space is vast, G-Express wants to report how many planets have become able to reach each other each time galaxies are connected.

You work on the technology development team at G-Express, and this program request has landed on your desk. Given the number of planets in each galaxy and the railway plan, build a program that reports, in real time, the number of planets reachable via the railways.

The first line gives the number of galaxies $N$ and the number of railways $M$.

Starting from the second line, $N$ lines give the number of planets in each of the $N$ galaxies, in order from galaxy 1. (The unit for counting planets is a trillion, $10^{12}$.)

Then, starting from line $N+2$, $M$ lines give railways connecting pairs of galaxies. Multiple railways can be built between the same pair of galaxies.

The input satisfies $2 \le N \le 100{,}000$ and $1 \le M \le 100{,}000$. Each galaxy has at most 100 trillion planets, and no galaxy has zero planets.

Each time a railway is connected, print the number of planets reachable via that railway, one value per line.

Because the input data is large, using fast input and output is recommended.