E. Тавас в пути
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тавас живет в Тавасполисе. В Тавасполисе 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