| Codeforces Round 299 (Div. 1) |
|---|
| Закончено |
Тавас живет в Тавасполисе. В Тавасполисе n городов, пронумерованных от 1 до n, соединенных n - 1 двунаправленными дорогами. Между любыми двумя городами есть путь. Также у каждой дороги есть длина.
Любимые строки Таваса — двоичные строки (содержащие только 0 и 1). Для любой двоичной строки типа s = s1s2... sk, определим T(s) — значение этой строки. T(s) вычисляется следующим способом:
Предположим, что в строке s ровно m блоков цифр 1 (блок цифр 1 — это максимальная подстрока s, которая содержит только единицы) длинами x1, x2, ..., xm.
Определим 
, где f — данная последовательность чисел (в частности, если m = 0, то T(s) = 0).
Тавас любит запросы. Он просит Вас ответить на q запросов. В каждом запросе он дает вам числа v, u, l, а вам следует вывести следующее число:
Рассмотрим дороги на пути из города v в город u: e1, e2, ..., ex.
Построим бинарную строку b длины x, такую, что: bi = 1 тогда и только тогда, когда l ≤ w(ei), где w(e) — длина дороги e.
Результатом запроса является строка T(b).
В первой строке ввода записаны целые числа n и q (2 ≤ n ≤ 105 и 1 ≤ q ≤ 105).
В следующей строке записано n - 1 целых чисел через пробел f1, f2, ..., fn - 1 (|fi| ≤ 1000).
В следующих n - 1 строках записана информация про дороги. В каждой строке содержатся целые числа v, u и w, означающие, что между городами v и u есть дорога длины w (1 ≤ v, u ≤ n и 1 ≤ w ≤ 109).
В следующих q строках записана информация о запросах. В каждой строке записаны целые числа v, u, l (1 ≤ v, u ≤ n, v ≠ u и 1 ≤ l ≤ 109).
Выведите ответ на каждый запрос на отдельной строке.
2 3
10
1 2 3
1 2 2
1 2 3
1 2 4
10
10
0
6 6
-5 0 0 2 10
1 2 1
2 3 2
3 4 5
4 5 1
5 6 5
1 6 1
1 6 2
1 6 5
3 6 5
4 6 4
1 4 2
10
-5
-10
-10
-5
0
