تلقى Askhat من NurlashKO شجرة ذات جذر هديةً في عيد ميلاده، تحتوي على $n$ رؤوس مرقمة من $1$ إلى $n$. الشجرة رسم بياني غير موجه ومتصل ولا يحتوي على دورات. جذر الشجرة هو الرأس ذو الرقم $1$. يكون الرأس $v$ سلفًا للرأس $u$ إذا وقع $v$ على أقصر مسار من $u$ إلى الجذر. السلف المشترك الأدنى لمتتالية الرؤوس $(x_1,x_2,\ldots,x_k)$ هو أبعد رأس عن الجذر يكون سلفًا لكل $x_i$ لجميع $1\le i\le k$، ويرمز إليه بـ$\operatorname{lca}(x_1,x_2,\ldots,x_k)$.

إضافةً إلى الهدية، أعد NurlashKO مهمة لـAskhat. في البداية، أعطاه متتالية طولها $m$ وهي $(a_1,a_2,\ldots,a_m)$، وكل عدد فيها هو رأس من الشجرة. قد تتكرر الرؤوس في المتتالية. ثم بدأ بطرح $q$ استعلامات، كل منها من أحد النوعين التاليين:

• $1\ pos\ v$: يطلب NurlashKO من Askhat تغيير القيمة في الموضع $pos$ إلى $v$، أي $a_{pos}=v$.
• $2\ l\ r\ v$: يطلب NurlashKO من Askhat إيجاد زوج $(x,y)$ يحقق $l\le x\le y\le r$ و$\operatorname{lca}(a_x,a_{x+1},\ldots,a_y)=v$، أو الإبلاغ عن عدم وجود مثل هذا الزوج.

قضى Askhat وقتًا طويلًا في دراسة الهدية، وهو الآن يريد مساعدتك.

الإدخال

يحتوي السطر الأول على ثلاثة أعداد صحيحة موجبة $n$ و$m$ و$q$: حجم الشجرة وطول المتتالية وعدد الاستعلامات. تحتوي الأسطر $n-1$ التالية على حواف الشجرة $(u_i,v_i)$ حيث $u_i\ne v_i$. يحتوي السطر التالي على $m$ أعداد صحيحة $a_1,a_2,\ldots,a_m$ ($1\le a_i\le n$)، وهي المتتالية التي أهداها NurlashKO إلى Askhat. يصف كل سطر من الأسطر $q$ التالية استعلامًا. إذا كان العدد الأول في الاستعلام يساوي $1$، فسيليه عددان $pos$ و$v$ ($1\le pos\le m$، $1\le v\le n$)، وهذا استعلام من النوع الأول. وإذا كان العدد الأول يساوي $2$، فستليه ثلاثة أعداد $l$ و$r$ و$v$ ($1\le l\le r\le m$، $1\le v\le n$)، وهذا استعلام من النوع الثاني. يُضمن وجود استعلام واحد على الأقل من النوع الثاني بين الاستعلامات $q$.

الإخراج

اطبع عددين $x$ و$y$ جوابًا لكل استعلام من النوع الثاني. إذا لم يوجد حل، فاطبع -1 -1 (دون علامات الاقتباس). إذا تعددت الحلول، فاطبع أيًا منها.

المهام الفرعية

تتكون هذه المسألة من أربع مهام فرعية، وتحقق اختبارات كل مهمة القيود الواردة في نص المسألة:

1. $1\le n,m,q\le100$. قيمتها 12 نقطة.
2. $1\le n,m,q\le500$. قيمتها 18 نقطة.
3. $1\le n,m,q\le2000$. قيمتها 26 نقطة.
4. $1\le n,m,q\le2\cdot10^5$. قيمتها 44 نقطة.

أمثلة

الإدخال 1

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

الإخراج 1

1 3
3 3
-1 -1

ملاحظة

• المتتالية: $[4,5,2,3]$.
• المقطع الفرعي هو $[4,5,2]$، و$v=1$. لدينا $\operatorname{lca}(4,5,2)=1$، والجواب $(1,3)$.
• استعلام تغيير؛ تصبح المتتالية $[4,5,5,3]$.
• المقطع الفرعي هو $[5,3]$، و$v=5$. لدينا $\operatorname{lca}(5)=5$، والجواب $(3,3)$.
• المقطع الفرعي هو $[4,5,5]$، و$v=1$. لدينا $\operatorname{lca}(4)=4$، و$\operatorname{lca}(5)=5$، و$\operatorname{lca}(4,5)=3$، و$\operatorname{lca}(5,5)=5$، و$\operatorname{lca}(4,5,5)=3$. لا يوجد حل.