Дано дерево с вершинами. На каждой вершине дерева написано одно число.
В этой задаче Вам следует ответить на запросов. Каждый запрос описывается тремя числами и . Чтобы ответить на запрос, сначала запишите числа, написанные на вершинах простого пути из в в том порядке, в котором они стоят. Затем ответ на запрос вычисляется следующим образом: складываются первые чисел полученной последовательности, вычитаются следующие чисел, затем снова добавляются следующие чисел, а затем снова вычитаются следующие чисел и так далее. Гарантируется, что количество вершин простого пути из в делится на .
Первая строка содержит два целых числа — количество вершин в дереве, и — количество запросов.
Вторая строка содержит последовательность из целых чисел — числа, написанные на вершинах.
Затем следует строка, описывающих ребра дерева. Каждая строка содержит пару целых чисел — вершины, соединенные ребром.
Последние строк описывают запросы, -я строка содержит три числа .
Выведите строк, -я строка содержит ответ на -й запрос.