Bittimaassa on n kaupunkia, ja tiedät jokaisen kaupungin asukasluvun. Kaupunkien välille aletaan rakentaa metroyhteyksiä. Keskus on joukko kaupunkeja, jossa mistä tahansa kaupungista toiseen pääsee metrolla.

Tehtäväsi on ilmoittaa jokaisen yhteyden rakentamisen jälkeen, kuinka monta asukasta asuu suurimmassa keskuksessa.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: kaupunkien määrä ja yhteyksien määrä. Kaupungit on numeroitu 1,2,\ldots,n.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: kunkin kaupungin asukasluku.

Lopuksi syötteessä on m riviä, jotka kuvaavat rakennettavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua a ja b: kaupunkien a ja b välille rakennetaan yhteys. Kaikki yhteydet ovat kaksisuuntaisia.

Mikään yhteys ei ole kaupungista itseensä, ja kahden kaupungin välille rakennetaan enintään yksi yhteys.

Tuloste

Ohjelmasi tulee tulostaa jokaisen yhteyden rakentamisen jälkeen suurimman keskuksen asukasluku.

Rajat

• 1 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le x_i \le 10^9
• 1 \le a,b \le n

Esimerkki

Syöte:

4 4
5 3 7 9
1 2
1 3
2 3
3 4

Tuloste:

9 15 15 24