Тавас Тавасполист амьдардаг. Тавасполист $n - 1$ ширхэг хоёр чиглэлт замаар холбогдсон $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хот байдаг. Дурын хоёр хотын хооронд замуудын тусламжтайгаар явж болдог. Мөн зам бүр тодорхой урттай байв.

Тавасын дуртай тэмдэгт мөр нь хоёртын тэмдэгт мөр буюу зөвхөн $0$ болон $1$-үүдээс тогтох тэмдэгт мөр юм. Дурын $s = s_{1}s_{2}... s_{k}$ хоёртын тэмдэгт мөрийн хувьд, $T(s)$-ээр түүний "сайн чанар" гэх ойлголтыг тэмдэглэе.

Энэ тэмдэгт мөрөнд $x_{1}, x_{2}, ..., x_{m}$ гэсэн уртуудтай $m$ ширхэг $1$-үүдийн хэрчим байгаа гэвэл $T(s) = \sum\limits_{i=1}^{m} f_{x_i}$ гэж тодорхойлъё.

Энд $f$ нь өгөгдсөн дараалал (Хэрэв $m = 0$ бол $T(s) = 0$). Мөн $s$ тэмдэгт мөрийн $1$-үүдийн хэрчим гэдэг нь дараалсан $1$-үүдээс тогтох хамгийн урт дэд тэмдэгт мөрийг хэлнэ.

Тавас чамаас $q$ хүсэлтийг нь гүйцэтгэж өгөхийг хүсчээ. Хүсэлт бүрт тэр чамд $v, u, l$ гэсэн тоонууд өгөх ба чи дараахь тоог хэвлэх ёстой:

$v$ хотоос $u$ хотруу очих замуудын дарааллыг авч үзье: $e_{1}, e_{2}, ..., e_{x}$.

Эхлээд дурын $i$ бүрийн хувьд $b_{i} = 1$ байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь $l ≤ w(e_{i})$ байхаар $x$ урттай $b$ бинар тэмдэгт мөрийг байгуулна. Энд $w(e)$ гэдгээр of $e$ замын уртыг тэмдэглэв.

Чи хүсэлт бүрт $T(b)$-г хэвлэх ёстой.

Оролт

Эхний мөрөнд $n$ ба $q$ ($2 ≤ n ≤ 10^{5}$; $1 ≤ q ≤ 10^{5}$) тоонууд байна.

Дараагийн мөрөнд $n - 1$ ширхэг $f_{1}, f_{2}, ..., f_{n - 1}$ ($|f_{i}| ≤ 1000$) бүхэл тоонууд зайгаар тусгаарлагдан байна.

Дараагийн $n - 1$ мөрөнд замуудын тайлбар байна. Мөр бүрт $v, u$ ба $w$ гэсэн тоонууд байх ба энэ нь $v$ болон $u$ хотыг $w$ урттай замаар холбосныг илэрхийлнэ ($1 ≤ v, u ≤ n$; $1 ≤ w ≤ 10^{9}$) .

Дараагийн $q$ мөрөнд хүсэлтүүдийг тайлбарлана. Мөр бүрт $v, u, l$ ($1 ≤ v, u ≤ n$, $v ≠ u$ ба $1 ≤ l ≤ 10^{9}$) гэсэн бүхэл тоонууд байрлана.

Гаралт

Хүсэлт бүрийн хариуг нэг мөрөнд хэвлэ.