Askhat קיבל מ־NurlashKO מתנה ליום הולדתו: עץ מושרש בעל $n$ קודקודים, הממוספרים מ־$1$ עד $n$. עץ הוא גרף לא מכוון קשיר שאין בו מעגלים. שורש העץ הוא הקודקוד שמספרו $1$. הקודקוד $v$ הוא אב קדמון של הקודקוד $u$ אם $v$ נמצא במסלול הקצר ביותר מ־$u$ אל השורש. האב הקדמון המשותף הנמוך ביותר של סדרת קודקודים $(x_1,x_2,\ldots,x_k)$ הוא הקודקוד הרחוק ביותר מהשורש שהוא אב קדמון של $x_i$ לכל $1 \le i \le k$, ומסמנים אותו $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$ וגם $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 \le 100$. ‏12 נקודות.
2. $1 \le n,m,q \le 500$. ‏18 נקודות.
3. $1 \le n,m,q \le 2000$. ‏26 נקודות.
4. $1 \le n,m,q \le 2\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$. מתקיים $lca(4,5,2)=1$, והתשובה היא $(1,3)$.
• שאילתת שינוי; הסדרה החדשה: $[4,5,5,3]$.
• תת־הקטע הוא $[5,3]$, ו־$v=5$. מתקיים $lca(5)=5$, והתשובה היא $(3,3)$.
• תת־הקטע הוא $[4,5,5]$, ו־$v=1$. מתקיים $lca(4)=4$, $lca(5)=5$, $lca(4,5)=3$, $lca(5,5)=5$, $lca(4,5,5)=3$. אין פתרון.