Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ tới ~n~. Bạn được cho một xâu nhị phân ~s_1s_2\dots s_n~. Tại thời điểm ~t~ cho mỗi ~t = 1, 2, \dots, n~ ta thực hiện thao tác như sau:

• Nếu ~s_t = 0~, đỉnh ~t~ và tất cả các cạnh hiện tại đang nối với đỉnh ~t~ sẽ bị xóa khỏi đồ thị;

• Nếu ~s_t = 1~, các cạnh mới sẽ được thêm vào giữa mọi cặp hai đỉnh kề của đỉnh ~t~ mà giữa hai đỉnh đó chưa có cạnh nối, liền sau đó đỉnh ~t~ và tất cả các cạnh hiện tại đang nối với đỉnh ~t~ sẽ bị xóa khỏi đồ thị.

Yêu cầu: Hãy đếm số lượng cặp ~2~ đỉnh phân biệt không kể thứ tự có thể đi đến được nhau thông qua một dãy các cạnh ngay trước mỗi thời điểm ~1, 2, \dots, n~.

Lưu ý: Cạnh hiện tại có thể là cạnh ban đầu hoặc cạnh được tạo ra ở thời điểm trước.

Input

• Dòng đầu chứa ~2~ số nguyên ~n, m~ (~1 \le n \le 2 \cdot 10^5~, ~0 \le m \le 4 \cdot 10^5~);

• Dòng thứ ~2~ chứa xâu nhị phân ~s~ gồm ~n~ kí tự;

• ~m~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u, v~ (~1 \le u, v \le n~) mô tả một cạnh ban đầu của đồ thị nối đỉnh ~u~ với đỉnh ~v~.

Các số trên cùng một dòng được cách nhau bởi dấu cách.

Output

• In ra ~n~ dòng, mỗi dòng là số lượng cặp đỉnh không kể thứ tự có thể đi đến được nhau ngay trước thời điểm ~t~ tương ứng (~t = 1, 2, \dots, n~).

Scoring

Sample Input 1

3 2
101
1 2
1 3

Sample Output 1

3
1
0

Sample Input 2

7 8
1011011
1 2
3 1
4 2
5 1
3 6
7 4
2 6
3 5

Sample Output 2

21
15
4
2
1
0
0

Notes

Trong ví dụ thứ nhất:

• Trước thời điểm ~1~: có ~3~ cặp đỉnh kết nối nhau: ~1~ và ~2~, ~1~ và ~3~, ~2~ và ~3~;

• Trước thời điểm ~2~: có ~1~ cặp đỉnh kết nối nhau: ~2~ và ~3~;

• Trước thời điểm ~3~: không có cặp đỉnh nào kết nối nhau.