Bạn được bố tặng 1 trò chơi giải đố hình cây gồm ~N~ đỉnh gốc tại 1, và 1 dãy ~A~ có ~M~ số. Chơi ~Q~ lượt, mỗi lượt bố sẽ cho bạn 1 yêu cầu thuộc 1 trong 2 dạng sau:

• Bố đưa bạn 2 số ~i~ và ~u~, bạn phải thay đổi ~a[i]~ thành ~u~.
• Bố đưa bạn 3 số ~l, r, u~, bạn phải tìm được cặp ~x, y~ (~l \le x \le y \le r~) sao cho nút cha chung gần nhất của ~a[x], a[x+1], \dots, a[y]~ là ~u~.

Yêu cầu: Bạn hãy tìm cách chiến thắng bố trong trò chơi này bằng cách in ra độ dài ngắn nhất của đoạn ~x, y~ thỏa mãn yêu cầu.

Input

• Dòng đầu tiên chứa 3 số ~N, M, Q~ (~N, M, Q < 200000~) cách nhau 1 dấu cách.
• ~N-1~ dòng tiếp theo là các cạnh của cây.
• Dòng tiếp theo chứa ~M~ số của dãy ~A~.
• ~Q~ dòng kế tiếp là các yêu cầu của mỗi lượt chơi, thuộc 1 trong 2 dạng:
  • ~1 i u~
  • ~2 l r u~

Output

• Với mỗi truy vấn loại 2, in ra độ dài ngắn nhất của đoạn ~x, y~. Nếu không có đoạn thỏa mãn, in -1.

Sample Input 1

3 3 2
1 2
1 3
1 2 3
2 1 1 1
2 2 3 1

Sample Output 1

1
2