Нудні деревовидні запити

Дано дерево з $n$ вершинами. На кожній вершині дерева записано одне число.

У цій задачі вам потрібно відповісти на $q$ запитів. Кожен запит визначається трьома числами $u,v$ і $k$. Щоб відповісти на запит, спочатку запишіть числа, які знаходяться на вершинах простого шляху від $u$ до $v$, у тому порядку, в якому вони зустрічаються. Потім відповідь на запит обчислюється так: додаються перші $k$ чисел отриманої послідовності, віднімаються наступні $k$ чисел, знову додаються наступні $k$ чисел, і так далі. Гарантується, що кількість вершин на простому шляху від $u$ до $v$ ділиться на $k$.

Вхідні дані

Перший рядок містить два цілі числа $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\le x_i,y_i\le n,x_i\ne y_i)$ — вершини, з'єднані ребром.

Останні $q$ рядків описують запити, $i$-й рядок містить три числа $u_i,v_i,k_i(1\le u_i,v_i,k_i\le n)$.

Вихідні дані

Виведіть $q$ рядків, де $i$-й рядок містить відповідь на $i$-й запит.

Приклади