Vùng đông dân nhất

Một quốc gia có $n$ thành phố đánh số từ $1$ đến $n$, thành phố thứ $i$ có $a_i$ người dân. Ban đầu chưa có con đường nào. Người ta lần lượt xây $m$ con đường hai chiều, con đường thứ $j$ nối thành phố $u_j$ với thành phố $v_j$.

Một vùng là một tập hợp thành phố lớn nhất mà từ mỗi thành phố trong đó có thể đi tới mọi thành phố khác trong tập bằng các con đường đã xây. Dân số của một vùng là tổng số dân của các thành phố trong vùng.

Sau khi xây xong mỗi con đường, hãy cho biết số vùng hiện có và dân số của vùng đông dân nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $u_j,v_j$. Có thể có $u_j=v_j$, và một cặp thành phố có thể được nối nhiều lần.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $j$ chứa hai số nguyên: số vùng và dân số của vùng đông dân nhất ngay sau khi xây con đường thứ $j$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• $1\le u_j,v_j\le n$

Ví dụ