URI Online Judge | 2577

Box Game

By Dilson Guimarães, UFMG BR Brasil

Timelimit: 1

Bruno and Henrique will play to pass the time. In the game they chose, there are N boxes. Within each box, there is a paper with a written whole number. In addition to the boxes, there are M-twines. Each of them ties two boxes.

The game works like this. First, Bruno chooses one of the boxes and removes it from the game, along with the strings that connect it to other boxes. Then Henry can choose a subset of any of the boxes such that if a box is chosen, all boxes attached to it must also be chosen.

Henry's punctuation is the sum of the numbers in the papers in the boxes chosen by him. Bruno's goal is to minimize the highest score Henry can choose. So for each box, Bruno wants to know what the highest score can be obtained by Henry if it is the box removed.

Input

The first line of the entry contains two integers N ( 1 < < 105 ) and M  ( 0 < M < 105 ), the number of boxes and the number of twines. The second line contains N integers C1, C2, ..., CN (-104 < Ci< 104) separated by space. The i-th of them corresponds to the number on the paper inside the i-th box. Each of the following M lines describes a twine. The i-th of them contains two integers Ai and Bi ( 1 < Ai < Bi < ), indicating that the ith striker ties the Ai-th and Bi-th boxes.

Output

The output must be composed of N integers separated by space. The ith integer shall correspond to the Punctuation that Henry can achieve if Bruno removes the i-th box.

Input Samples Output Samples

3 2
5 5 -5
1 2
2 3

0 5 10

4 4
5 5 -5 -10
1 2
2 3
2 4
3 4

0 5 0 5