Cow Land הוא פארק שעשועים מיוחד לפרות: הן משוטטות, אוכלות עשב טעים ומבקרות באטרקציות שונות (רכבת ההרים לפרות פופולרית במיוחד).

יש $N$ אטרקציות שונות ($2 \leq N \leq 10^5$). זוגות מסוימים מחוברים בשבילים, $N-1$ בסך הכול, כך שבין כל שתי אטרקציות יש מסלול יחיד המורכב משבילים אלה. לכל אטרקציה $i$ ערך הנאה שלם $e_i$, שעשוי להשתנות ביום: חלקן מושכות יותר בבוקר ואחרות בשעות אחר הצהריים המאוחרות.

פרה העוברת מ־$i$ ל־$j$ חווה את כל האטרקציות במסלול מ־$i$ ל־$j$. למרבה הפלא, ההנאה הכוללת היא XOR לפי סיביות של כל הערכים במסלול, כולל $i$ ו־$j$.

עזרו לפרות למצוא את ערכי ההנאה של המסלולים המתוכננים לביקור הבא ב־Cow Land.

קלט

השורה הראשונה מכילה $N$ ומספר שאילתות $Q$ ($1 \leq Q \leq 10^5$). הבאה מכילה $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). $N-1$ השורות הבאות מתארות שבילים בשני מזהים שלמים $a$ ו־$b$ (שניהם בטווח $1 \ldots N$). $Q$ האחרונות מתארות עדכון $e_i$ או שאילתת הנאה ממסלול. "1 $i$ $v$" מעדכן את $e_i$ ל־$v$, ו־"2 $i$ $j$" שואל על ההנאה בין $i$ ו־$j$.

בנתוני בדיקה ששווים לכל היותר 50% מהנקודות, ערכי האטרקציות אינם משתנים.

פלט

לכל שאילתה "2 $i$ $j$" הדפיסו בשורה אחת את ההנאה במסלול מ־$i$ ל־$j$.

דוגמאות

קלט 1

5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3

פלט 1

21
20
4
20

מחבר הבעיה: Charles Bailey