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