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ố. Luật chơi như sau:

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 ≤ x ≤ y ≤ r)\) sao cho nút cha chung gần nhất của \(a[x], a[x+1], ...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.

Dữ liệu:

• 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\)

Kết quả:

• 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.

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bài có \(1≤ n ≤ 5000\)

• 60% số test tiếp theo ứng với 60% số điểm của bài có \(5000 ≤ n ≤ 200000\) ## Sample Input

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

  ## Sample Output

  1
  2