Ở thị trấn Lạc Sơn có ~N~ căn nhà được đánh số từ ~1~ đến ~N~ và ~M~ người dân được đánh số từ ~1~ đến ~M~. Mỗi người sống trong đúng một căn nhà, và mỗi căn nhà có nhiều nhất một người ở. Các căn nhà nằm trên sườn núi. Với mỗi nhà ~i~, có một đường trượt một chiều từ nhà ~i~ tới nhà ~r_i~. Có đúng một nhà ~s~ thỏa mãn ~r_s=s~; đây là nhà ở chân núi. Nếu xem mỗi đường trượt là một cạnh hướng về chân núi, các cạnh này tạo thành một cây gốc tại ~s~. Vì vậy từ một căn nhà bất kỳ, đi theo các đường trượt sẽ dẫn tới chân núi.

Những người dân quen biết nhau theo một vòng tròn: người ~i~ quen người ~i-1~ và ~i+1~; riêng người ~1~ quen người ~2~ và ~M~, người ~M~ quen người ~M-1~ và ~1~.

Có ~Q~ sự kiện, thuộc một trong hai loại:

• Loại ~1~: cho hai nhà ~a, b~. Nếu cả hai nhà đều có người, hai người đang sống ở hai nhà này đổi chỗ cho nhau. Nếu một trong hai nhà trống thì người ở nhà còn lại chuyển sang nhà trống đó; nếu cả hai nhà đều trống thì không có gì thay đổi.

• Loại ~2~: cho một người ~p~ và một số ~R~. Người ~p~ muốn tổ chức một bữa tiệc. Cậu ta được chọn một trong hai hướng quanh vòng tròn bạn bè, rồi mời một đoạn liên tiếp bắt đầu từ ~p~ theo hướng đó. Nói cách khác, nếu mời ~K~ người thì người ~p~ là một trong hai đầu của đoạn gồm ~K~ người liên tiếp trên vòng tròn. Một nhóm khách mời hợp lệ nếu tồn tại một căn nhà làm địa điểm tổ chức sao cho mọi người trong nhóm có thể đi từ nhà hiện tại của mình tới địa điểm đó bằng không quá ~R~ đường trượt.

Với mỗi sự kiện loại ~2~, hãy tìm số người lớn nhất có thể được mời.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, M, Q~ ~(1 \le M \le N \le 10^5, 1 \le Q \le 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên ~r_1, r_2, \dots, r_N~ ~(1 \le r_i \le N)~. Có đúng một chỉ số ~s~ sao cho ~r_s=s~, và các đường trượt tạo thành một cây gốc tại ~s~.

• Dòng thứ ba chứa ~M~ số nguyên ~h_1, h_2, \dots, h_M~ ~(1 \le h_i \le N)~, trong đó ~h_i~ là nhà ban đầu của người ~i~. Các giá trị ~h_i~ đôi một khác nhau.

• Trong ~Q~ dòng tiếp theo, mỗi dòng mô tả một sự kiện:

  • ~1\ a\ b~ ~(1 \le a,b \le N, a \ne b)~: đổi cư dân của hai nhà ~a~ và ~b~.

  • ~2\ p\ R~ ~(1 \le p \le M, 1 \le R < N)~: truy vấn bữa tiệc do người ~p~ tổ chức với giới hạn ~R~ đường trượt.

Output

Với mỗi sự kiện loại ~2~, in ra một dòng chứa số người lớn nhất có thể được mời.

Scoring

Sample Input 1

8 4 9
1 1 1 2 2 3 3 6
4 7 5 8
2 1 1
2 2 2
1 7 6
2 2 1
1 4 8
2 4 1
2 3 2
1 5 2
2 3 1

Sample Output 1

1
2
1
2
2
2

Notes

• Ở truy vấn đầu tiên, người ~1~ đang ở nhà ~4~. Với ~R=1~, nếu mời thêm người kề bên nào trên vòng tròn thì địa điểm chung gần nhất đều quá xa, nên chỉ mời được một người.

• Ở truy vấn thứ hai, người ~2~ đang ở nhà ~7~ và ~R=2~. Có thể mời thêm người ~3~ ở nhà ~5~ rồi chọn nhà ~1~ làm địa điểm tổ chức, nhưng không thể mời ba người cùng lúc.

• Sau sự kiện ~1\ 7\ 6~, người ~2~ chuyển từ nhà ~7~ sang nhà ~6~. Vì vậy ở truy vấn tiếp theo với ~R=1~, người ~2~ không thể mời thêm người nào. Sau sự kiện ~1\ 4\ 8~, người ~1~ và người ~4~ đổi chỗ; khi người ~4~ làm chủ tiệc với ~R=1~, có thể mời thêm người ~3~ và chọn nhà ~2~ làm địa điểm tổ chức.