Khu trải nghiệm của trường là một mê cung gồm ~n~ phòng, đánh số từ ~1~ đến ~n~. Tại mỗi phòng ~i~ có đúng một cửa ra và có thể có nhiều cửa vào. Qua cửa ra này, ta đi đến phòng ~f(i)~ và mất ~w(i)~ giây. Có thể xảy ra ~f(i) = i~, nghĩa là qua cửa rồi ta lại trở về chính phòng ~i~. Trong mỗi phòng ~i~ có đặt một phần thưởng trị giá ~a(i)~.

Một người đứng ở phòng ~x~ và liên tục đi qua cửa của phòng mình đang đứng. Vì mỗi phòng chỉ có một cửa ra nên hành trình của người đó là hoàn toàn xác định. Mỗi lần đi qua một cửa được tính là một bước, bất kể cửa đó mất bao nhiêu giây; cửa dẫn ngược lại chính phòng đang đứng cũng tính là một bước.

Ban tổ chức cần xử lí ~q~ thao tác, mỗi thao tác thuộc một trong năm loại sau:

• Loại ~1~, cú pháp ~1 u v~: Hai người đứng ở phòng ~u~ và phòng ~v~, cùng xuất phát và mỗi lần cùng đi một bước. Hãy cho biết số bước ít nhất ~t \ge 0~ để sau đó hai người ở CÙNG một phòng; nếu điều đó không bao giờ xảy ra thì trả lời ~-1~.

• Loại ~2~, cú pháp ~2 u k~: Xuất phát từ phòng ~u~ và đi đúng ~k~ bước. Hãy cho biết phòng dừng lại và tổng thời gian đã đi.

• Loại ~3~, cú pháp ~3 u k~: Xét ~k~ phòng đầu tiên trong hành trình xuất phát từ ~u~, tức các phòng sau ~0, 1, \dots, k - 1~ bước (một phòng đi qua nhiều lần vẫn tính nhiều lần). Hãy cho biết giá trị phần thưởng lớn nhất trong các phòng đó.

• Loại ~4~, cú pháp ~4 v k~: Hãy đếm số phòng ~x~ sao cho xuất phát từ ~x~, sau không quá ~k~ bước thì tới được phòng ~v~ (phòng ~v~ được tính, ứng với ~0~ bước).

• Loại ~5~, cú pháp ~5 x c~: Thay phần thưởng của phòng ~x~ bằng giá trị ~c~. Thao tác này không in ra kết quả.

Hãy xử lí lần lượt ~q~ thao tác theo đúng thứ tự đã cho.

Input

• Dòng ~1~ chứa hai số nguyên ~n~ và ~q~ ~(1 \le n, q \le 2 \times 10^5)~;

• Dòng ~2~ chứa ~n~ số nguyên ~f(1), f(2), \dots, f(n)~ ~(1 \le f(i) \le n)~;

• Dòng ~3~ chứa ~n~ số nguyên ~w(1), w(2), \dots, w(n)~ ~(1 \le w(i) \le 10^9)~;

• Dòng ~4~ chứa ~n~ số nguyên ~a(1), a(2), \dots, a(n)~ ~(0 \le a(i) \le 10^9)~;

• ~q~ dòng tiếp theo, mỗi dòng mô tả một thao tác theo đúng cú pháp ở trên, với ~1 \le u, v, x \le n~, ~1 \le k \le 10^9~ và ~0 \le c \le 10^9~.

Output

• Ứng với mỗi thao tác loại ~1, 3, 4~, ghi ra một dòng chứa một số nguyên là kết quả của thao tác đó;

• Ứng với mỗi thao tác loại ~2~, ghi ra một dòng chứa hai số nguyên cách nhau bởi dấu cách: phòng dừng lại và tổng thời gian đã đi;

• Thao tác loại ~5~ không ghi ra kết quả.

Scoring

Sample Input 1

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

Sample Output 1

2
3 9
9
3
7

Notes

Mê cung có chu trình ~2 \rightarrow 3 \rightarrow 2~; phòng ~1~ dẫn vào phòng ~2~; phòng ~5~ dẫn vào phòng ~1~; phòng ~4~ dẫn vào phòng ~3~.

Thao tác ~1~: hai người ở phòng ~5~ và phòng ~4~ đi theo ~(5, 4) \rightarrow (1, 3) \rightarrow (2, 2)~, gặp nhau sau ~2~ bước.

Thao tác ~2~: ~5 \rightarrow 1 \rightarrow 2 \rightarrow 3~, tổng thời gian ~3 + 5 + 1 = 9~.

Thao tác ~3~: ba phòng đầu là ~1, 2, 3~ với phần thưởng ~7, 2, 9~; lớn nhất là ~9~.

Thao tác ~4~: các phòng tới được phòng ~2~ trong không quá ~1~ bước là ~2, 1~ và ~3~.

Thao tác ~5~: phần thưởng phòng ~3~ đổi thành ~0~.

Thao tác ~6~: vẫn ba phòng ~1, 2, 3~ nhưng phần thưởng nay là ~7, 2, 0~; lớn nhất là ~7~.