• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۴۰ مگابایت

---

غول‌پیکرها به همراه مینو و پگاه بعد از یک سفر سخت و طولانی بالأخره به شهرجادویی رسیدند. سُس بیژن، شکلات پارمیدا، روغن لادن، شیرین‌عسلِ جذّاب و همه‌ی خوراکی‌های دیگر از آن‌ها استقبال کردند. ولی بلافاصله بعد از اتمام پذیرایی، ساکنین شهرجادویی مشکلی که به تازگی برای آن‌ها پیش آمده را با پگاه و مینو مطرح کردند تا شاید بتوانند آن را حل کنند.

شهر جادویی شامل \(n\) شهرستان است که بعضی آن‌ها با یک جاده به‌هم متصل شده‌اند. می‌دانیم بین هر دو شهرستان دقیقاً یک مسیر وجود دارد. (هر مسیر از تعدادی جاده تشکیل شده است.) به علاوه، هر شهرستان در شهرجادویی تعدادی درخت آلبالو دارد.

ساکنان شهر جادویی \(q\) مشکل دارند، که در مشکل \(i\)اُم می خواهند بدانند اگر مسیر شهرستان ‌\(u_i\) و \(v_i\) را با شروع از \(u_i\) و \(k_i\) تا \(k_i\) تا طی کنند تاجایی که دیگر نتوانند به مسیر خود ادامه دهند در مجموع چندتا درخت آلبالو می‌بینند. (اگر از همه‌ی شهرستان‌های مسیر بین ‌\(u_i\) و \(v_i\) عبور کنیم؛ مسیر را یکی‌یکی طی کرده‌ایم.)

همچنین میدانیم اگر \(ans_i\) پاسخ مشکل \(i\)اُم باشد: \[k_1 = x_1\] \[k_i = ans_{i-1}\oplus x_i \ \ \ \ \ i > 1\] به مینو و پگاه کمک کنید تا خودشان را به ساکنان شهرجادویی ثابت کنند.

ورودی

در خط اوّل ورودی دو عدد \(n\) و \(q\) داده می‌شود. \[1 \leq n, q \leq 100\ 000\] در خط بعد \(n\) عدد آمده که عدد \(i\)اُم \(t_i\) (تعداد درخت‌های آلبالوی شهرستان\(i\)) است. \[1 \leq t_i \leq 10^9\]

پس از آن در \(n-1\) خط جاده‌های شهر جادویی داده می‌شوند. هر خط شامل دو عدد \(u\) و \(v\) است که شهرستان‌های دو سر جاده را مشخص می‌کنند. \[1 \leq u,v \leq n\] سپس در \(q\) خط بعد در هر خط سه عدد \(u_i\) و \(v_i\) و \(x_i\) می‌آید که معرف مشکل ‌‌‌\(i\)اُم هستند. \[1 \leq u_i, v_i \leq n\] \[1 \leq x_i \leq 10^{15}\]

خروجی

خروجی شامل \(q\) خط است که خط \(i\)اُم آن برابر \(ans_i\) می‌باشد.

مثال

ورودی نمونه

4 5
1 2 3 4
1 2
2 3
1 4
1 4 1
1 4 1
1 2 2
1 3 4
1 4 3

خروجی نمونه

5
1
1
1
1