Masala I

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.