Cà vạt

Trên một hòn đảo có \(N\) ngôi làng, mỗi làng ban đầu yêu thích một màu cà vạt khác nhau. Làng thứ \(i\) có \(s_i\) người. Giữa các làng có \(M\) con đường hai chiều nối trực tiếp một số cặp làng.

Theo thời gian, mỗi tuần một làng có thể thuyết phục một làng láng giềng đổi sang màu cà vạt của mình. Việc này chỉ xảy ra nếu tổng số người yêu thích màu cà vạt của làng đi thuyết phục nhiều hơn hoặc bằng tổng số người yêu thích màu của làng bị thuyết phục. Ban đầu, mỗi làng chỉ có dân trong làng mình ủng hộ màu cà vạt của chính họ.

Quá trình thuyết phục tiếp tục cho đến khi tất cả người dân trên đảo đều yêu thích cùng một màu cà vạt.

Bạn cần xác định: màu cà vạt ban đầu của những làng nào có thể trở thành màu cà vạt duy nhất cuối cùng của toàn đảo.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 200\,000\), \(0 \le M \le 200\,000\)) --- số làng và số con đường.
• Dòng thứ hai chứa \(N\) số nguyên \(s_1, s_2, \ldots, s_N\) (\(1 \le s_i \le 10^9\)) --- dân số mỗi làng.
• Mỗi trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le N\), \(a \ne b\)) --- mô tả một con đường nối làng \(a\) và \(b\).

Đảm bảo rằng toàn bộ các làng tạo thành một đồ thị liên thông.

\OutputFile

In ra một chuỗi nhị phân có \(N\) ký tự. Ký tự thứ \(i\) là 1 nếu màu cà vạt của làng \(i\) có thể trở thành màu cà vạt chung cuối cùng, ngược lại in 0.

\Examples

\beginexample
\exmp4 4
2 2 4 3
1 2
1 3
2 3
3 4
1110

\endexample

\Scoring

• Subtask 1 (15 điểm): \(N \le 2\,000\), \(M \le 2\,000\)
• Subtask 2 (15 điểm): \(s_1 \ge s_2 \ge \cdots \ge s_N\), và đồ thị có dạng cây. Khi đặt gốc của cây là \(1\), khi tổ tiên của một đỉnh \(u\) bất kỳ là \(p\) thì (\(1 \le p \lt u \le n\)).
• Subtask 3 (15 điểm): Các làng được nối nếu và chỉ nếu \(|a - b| = 1\)
• Subtask 4 (30 điểm): Có tối đa 10 giá trị dân số khác nhau
• Subtask 5 (25 điểm): Không có giới hạn gì thêm

Note

Giải thích ở test ví dụ đề bài:

Số đầu tiên được ghi là số 1 bởi vì làng 1 có thể là làng có màu kết thúc -- ta có quá trình như sau: Làng 1 bắt đầu với việc thuyết phục làng 2 (lúc này số người yêu thích màu của các làng là 2 và 2). Sau khi thuyết phục số người yêu thích màu của làng 1 là 4. Tiếp theo thuyết phục làng 3 (hiện giờ số người yêu thích màu của các làng là \(4\) và \(4\)). Số người yêu thích màu 1 trở thành 8. Cứ như vậy thuyết phục thêm làng thứ 4.