Nitori mở thương hiệu dưa chuột mới, có ~n~ chi nhánh được kết nối với nhau theo dạng cây. Có tất cả ~C~ loại dưa chuột, cửa hàng thứ ~i~ bán loại dưa chuột ~a_i~. Ngày hôm nay có ~q~ khách hàng ghé thăm các cửa hàng của cô, mỗi khách hàng thứ ~i~ ghé thăm cửa hàng ~x_i~ và đặt loại dưa chuột ~y_i~, có thể cửa hàng ~x_i~ không bán loại dưa chuột ~y_i~ nên cô cần tới cửa hàng gần nhất lấy.

Hỏi với mỗi khách hàng, thời gian tối thiểu cần để phục vụ là bao nhiêu?

Input

• Dòng đầu tiên là số nguyên dương ~1 \le n \le 10000~.
• ~n - 1~ dòng tiếp theo là đường đi trực tiếp giữa 2 cửa hàng trong hệ thống.
• Dòng tiếp theo là số nguyên dương ~C \le n~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le a_i \le C~.
• Dòng tiếp theo là số nguyên dương ~1 \le q \le 10000~.
• ~q~ dòng tiếp theo dòng thứ ~i~ gồm số nguyên dương ~1 \le x_i \le n~ và ~1 \le y_i \le C~.

Output

• In ra ~q~ dòng thời gian tối thiểu cần phục vụ khách hàng.

Sample Test

Input:

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

Output:

1
2
0
1
2
2
3
3