Anh nông dân John có \(N\) con bò được đánh số từ \(1\) đến \(N\) và các mối quan hệ thân thiết của những con bò này được mô tả bởi một cây. Vào một hôm, thật không may khi có một dịch bệnh đang lan truyền khắp nơi quanh đó.

Vào ngày đầu tiên, một số con bò đã bị bệnh. Sau mỗi đêm, mỗi con bò đã bị lây nhiễm sẽ lây bệnh cho các con bò mà chúng thân thiết. Một khi con bò đã bị nhiễm bệnh thì con bò đó sẽ không khỏi bệnh. Sau vài đêm, John đã bắt đầu nhận ra vấn đề, vì vậy anh ấy sẽ kiểm tra những con bò của mình để xem những con nào bị mắc bệnh.

Bạn nhận được \(Q\) giá trị khác nhau mô tả số lượng đêm từ ngày đầu tiên đến ngày John kiểm tra đàn bò, các giá trị đó nằm trong đoạn \([0, N]\). Với mỗi số lượng đêm, hãy tìm số lượng tối thiểu các con bò bị nhiễm bệnh vào ngày đầu tiên, hoặc cho biết số lượng đêm đó không tồn tại so với thông tin mà John kiểm tra từ đàn bò của mình.

Input

• Dòng thứ nhất chứa một số nguyên \(N\) \((2 \le N \le 10^5)\) mô tả số lượng con bò.
• Dòng tiếp theo chứa một xâu nhị phân \(S\) độ dài \(N\), với \(S_i\) (\(S_i\) là kí tự thứ \(i\) của xâu \(S\), \(i \in [1, N]\)) là \(1\) nếu con bò thứ \(i\) bị bệnh vào ngày John kiểm tra hoặc \(0\) trong trường hợp ngược lại.
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u, v\) mô tả 2 con bò thứ \(u\) và \(v\) quen biết nhau.
• Dòng tiếp theo gồm số nguyên \(Q\) \((1 \le Q \le 20)\) mô tả số lượng truy vấn.
• \(Q\) Dòng cuối cùng, dòng thứ \(j\) gồm số nguyên \(x_j\) mô tả số lượng đêm trước ngày John kiểm tra.

Output

• In ra \(Q\) dòng, dòng thứ \(j\) hãy in ra số lượng con bò bị nhiễm bệnh ở ngày đầu tiên, nếu không có trường hợp nào khả thi, hãy in ra \(-1\).

Scoring

• Subtask 1: \(N \le 10\).
• Subtask 2: Tất cả các con bò đều bị lây nhiễm bệnh.
• Subtask 3: \(N \le 400\).
• Subtask 4: Không có giới hạn gì thêm.

Example

5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0

1
1
1
1
2
5

10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10

10
3
2
1
1
1
1
1
1
1
1

5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5

3
1
1
-1
-1
-1