Програмчлалын олимпиадын бодлогын архив

     Таньд холбогдсон циклгүй граф буюу мод өгөгдсөн. Дурын оройноос бусад оройнууд тус бүрт очих цор ганц зам олддог. Тухайн модны оройнууд 1-с N хүртэл дугаарлагдсан ба орой бүр 10^9-с абсолют утгаараа үл хэтрэх утгатай болно. 1-р оройг тухайн модны үндэс гэж үзнэ. Мөн M ширхэг цуврал асуулга өгөгдөх ба асуулга бүр V ба K тоонуудыг агуулна. Энд V нь тухайн модны нэг оройн дугаар ба V орой дээр үндэстэй дэд модны хувьд утгаараа яг К тоотой тэнцүү хичнээн орой байгаад хариулна.

1 <= N, M <= 100000 N нь нийт оройн тоо ба M нь асуулгын тоо

a[i] <= |10^9| орой бүр дээрх тоон утга

1 <= V <= N цуврал асуулга бүрийн хувьд өгөгдөх оройн дугаар

К <= |10^9| цуврал асуулга бүрийн хувьд өгөгдөх тоон утга

Input

Эхний мөрөнд нийт оройн тоо N ба нийт асуулгын тоо M зайгаар тусгаарлагдан өгөгдөнө. Хоёр дахь мөрөнд N ширхэг a[i] тоо зайгаар тусгаарлагдан нэг мөрөнд өгөгдөх ба энэ нь i - р (1 <= i <= N) орой бүрийн тоон утга юм. Дараагийн N-1 ширхэг мөрөнд модны холболтын мэдээлэл p, q тоонууд өгөгдөнө. Энэ нь p болон q оройнуудын хооронд ирмэг байгааг илэрхийлнэ. (p != q, 1 <= p, q <= N) Дараагийн M мөр тус бүрт V, K тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Output

M ширхэг мөр тус бүрт нэг тоо байх ба энэ нь V дээр үндэстэй дэд модны хувьд К - тай утгаараа тэнцүү байх оройн тоог хэвлэнэ.

Example

Input:
6 2

3 5 3 4 5 6

1 2
2 4
5 2
3 1
3 6

2 5
3 6

Output:
2
1