Дано дерево с $n$ вершинами. На каждой вершине дерева написано одно число. В этой задаче Вам следует ответить на $q$ запросов. Каждый запрос описывается тремя числами $u, v$ и $k$. Чтобы ответить на запрос, сначала запишите числа, написанные на вершинах простого пути из $u$ в $v$ в том порядке, в котором они стоят. Затем ответ на запрос вычисляется следующим образом: складываются первые $k$ чисел полученной последовательности, вычитаются следующие $k$ чисел, затем снова добавляются следующие $k$ чисел, а затем снова вычитаются следующие $k$ чисел и так далее. Гарантируется, что количество вершин простого пути из $u$ в $v$ делится на $k$. \InputFile Первая строка содержит два целых числа $n~(1 \le n \le 10^5)$ --- количество вершин в дереве, и $q~(1 \le q \le 10^5)$ --- количество запросов. Вторая строка содержит последовательность из $n$ целых чисел $a_1, a_2, \dots, a_n~(1 \le a_i \le 10000)$ --- числа, написанные на вершинах. Затем следует $n - 1$ строка, описывающих ребра дерева. Каждая строка содержит пару целых чисел $x_i, y_i~(1 \leq x_i,y_i \leq n, x_i \ne y_i)$ --- вершины, соединенные ребром. Последние $q$ строк описывают запросы, $i$-я строка содержит три числа $u_i, v_i, k_i~(1 \le u_i, v_i, k_i \le n)$. \OutputFile Выведите $q$ строк, $i$-я строка содержит ответ на $i$-й запрос.