Masala #RGNGFYMOZL

Sizga do'stingiz $n$ ta tugundan tashkil topgan $t$ daraxt bergan. Har bir tugunda sonlar yozilgan ya'ni $i$ -chi tugun uchun unda yozilgan son - $a_{i}$ , sizga $q$  ta so'rovga javob berishingiz kerak. Har bir so'rovda $x$, $l$ va $r$($1 \le l \le r \le n$) berilgan. Aytaylik qanaqadir $i$ va $j$ tugunlar uchun ular orasidagi ma'sofani $d(i,j)$ deb belgilab olaylik, sizni vazifangiz shunday $a_{i}$ lar yig'indisini topishingiz kerak $l \le d(x, i) \le r$ sharti bajarilishi kerak. Rasmiy ravishda:

Birinchi qatorda ikkita natural sonlar $n$ va $q$($2 \le n,q \le 10^5$, ) - Daraxtdagi tugunlar soni va so'rovlar soni.

Ikkinchi qatorda $n$ ta natural sondan tashkil topgan $a$ massiv ($1 \le a_{i} \le 10^9$).

Keyingi $n-1$ ta qatorda $t$ daraxtni ikkita tugunlari $u$ va$v$($1 \le u,v \le n$) - $u$ va $v$ ni bog'lab turuvchi yo'l.

Keyingi $q$ ta qatorda $x$, $l$ va $r$($1 \le x \le n$, $1 \le l \le r \le n$). Agar $[l,r]$ oralig'ida qaysidir tugun yo'q bolsa u tugundagi qiymatini $0$ deb olib ketishingiz mumkin.

Har bir so'rovga javobni chiqaring.