Запити на дереві

Дано зв'язний граф з $n$ вершинами та $n-1$ ребром, тобто дерево. Вершина $1$ є коренем дерева. На вершині $v$ записано ціле число $a_v$. Вартість дерева визначається як XOR сума всіх його значень. Дано $q$ запитів, кожен з яких містить два цілі числа $v$ та $x$. Кожен запит змінює всі значення $a_u$ на $a_u\oplus x$, де $u$ належить піддереву вершини $v$, а $\oplus$ позначає операцію "виключне або". Як ми всі знаємо, ця задача є дуже простою для наших учасників, але якби все було так просто, ця задача не з'явилася б на цій олімпіаді. Ви знаєте, що деякі запити були змінені злим Антоном. Тому вам потрібно знайти суму вартостей за модулем $998244353$ всіх $2^q$ дерев, які можна отримати, застосовуючи деякі (можливо, ніякі) запити до дерева.

Вхідні дані

Перший рядок містить два цілих числа $n$ ($1\le n\le 2\cdot 10^5$) та $q$ ($1\le q\le 2\cdot 10^5$) — кількість вершин у дереві та кількість запитів відповідно.

Другий рядок містить $n$ цілих чисел $a_i$ ($0\le a_i<2^{60}$) — значення, записані на вершинах дерева.

Наступні $n-1$ рядки містять два цілих числа $u$ та $v$ кожен — ребра заданого дерева.

Наступні $q$ рядків містять два цілих числа $v$ ($1\le v\le n$) та $x$ ($0\le x<2^{60}$) кожен — опис запитів.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Оцінювання

1. ($7$ балів): $q\le 2$;

2. ($12$ балів): $q\le 10$;

3. ($16$ балів): $q\le 20$;

4. ($18$ балів): $a_i,x<2$;

5. ($13$ балів): $a_i,x<1024$;

6. ($15$ балів): $a_i,x<2^{18}$;

7. ($19$ балів): без додаткових обмежень.