Askhat は誕生日に NurlashKO から、$1$ から $n$ までの番号が付いた $n$ 頂点の根付き木をプレゼントとしてもらいました。木とは、閉路を持たない連結な無向グラフです。木の根は番号 $1$ の頂点です。頂点 $v$ が頂点 $u$ から根への最短経路上にあるとき、$v$ を $u$ の祖先といいます。頂点列 $(x_1,x_2,\ldots,x_k)$ の最小共通祖先とは、すべての $1\le i\le k$ について $x_i$ の祖先である頂点のうち、根から最も遠い頂点です（$\operatorname{lca}(x_1,x_2,\ldots,x_k)$）。
プレゼントに加えて、NurlashKO は Askhat に課題を用意しました。まず、長さ $m$ の列 $(a_1,a_2,\ldots,a_m)$ を伝えました。列の各数は木の頂点を表し、同じ頂点が複数回現れてもかまいません。その後、次の 2 種類のいずれかである $q$ 個のクエリを出し始めました。
- $1\ \mathit{pos}\ v$ — NurlashKO は Askhat に、位置 $\mathit{pos}$ の値を $v$ に変更するよう求めます。すなわち $a_{\mathit{pos}}=v$ とします。
- $2\ l\ r\ v$ — NurlashKO は Askhat に、$l\le x\le y\le r$ かつ $\operatorname{lca}(a_x,a_{x+1},\ldots,a_y)=v$ を満たす組 $(x,y)$ を見つけるか、そのような組が存在しないことを報告するよう求めます。
Askhat はこのプレゼントを調べるのに長い時間を費やしており、あなたの助けを求めています。
入力
最初の行には 3 つの正の整数 $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$ の場合、その後に 2 つの数 $\mathit{pos},v$（$1\le\mathit{pos}\le m,1\le v\le n$）が続き、1 種類目のクエリを表します。最初の数が $2$ の場合、その後に 3 つの数 $l,r,v$（$1\le l\le r\le m,1\le v\le n$）が続き、2 種類目のクエリを表します。$q$ 個のクエリのうち少なくとも 1 個は 2 種類目であることが保証されます。
出力
2 種類目の各クエリに対して、答えとなる 2 つの数 $x,y$ を出力してください。解が存在しない場合は -1 -1 を出力してください。解が複数ある場合は、どれを出力してもかまいません。
小課題
この問題は 4 つの小課題からなり、各小課題のテストは問題文の制約を満たします。
- $1\le n,m,q\le100$。12 点。
- $1\le n,m,q\le500$。18 点。
- $1\le n,m,q\le2000$。26 点。
- $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$ です。解は存在しません。