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 \cdot 10^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$ ไม่มีคำตอบ