Một vùng biển bao gồm ~n~ hòn đảo đánh số từ 1 đến ~n~ và được kết nối bởi ~n - 1~ tuyến đường biển. Từ một hòn đảo bạn có thể đến được mọi hòn đảo khác chỉ qua các tuyến đường này.

Mỗi hòn đảo thuộc địa phận của chính xác một quốc gia, các quốc gia được đánh số từ 1 đến ~n~. Hòn đảo ~v~ thuộc địa phận của quốc gia ~t_v~. Lưu ý một quốc gia có thể bao gồm bất kì tập con các hòn đảo nào, và có thể bạn không thể di chuyển giữa hai hòn đảo cùng quốc gia chỉ bằng cách đi qua các hòn đảo cùng quốc gia khác.

Bạn là một thợ săn kho báu và đang sinh sống ở hòn đảo 1. Mỗi hòn đảo có một mức thuế nhất định cho mỗi kho báu bạn mang qua. Ở hòn đảo ~v~, mức thuế là ~c_v~ đồng.

Bạn được biết hai loại sự kiện sau có thể xảy ra:

1. Hòn đảo ~v~ trở thành địa phận của quốc gia ~t_{new}~.
2. Có ~k~ kho báu sẽ xuất hiện ở các hòn đảo ~a_1, a_2, \dots, a_k~, khi đó bạn sẽ di chuyển đến tất cả các hòn đảo và mang kho báu ở từng hòn đảo về hòn đảo 1. Sau đó bạn sẽ chọn một hòn đảo ~v~ bất kì thuộc địa phận của quốc gia ~t~ và bạn sẽ chỉ phải trả thuế ~c_v \times num_v~ đồng với ~num_v~ là số lượng kho báu bạn mang qua hòn đảo ~v~.

Với mỗi sự kiện 2, bạn cần tính mức thuế lớn nhất mà bạn phải trả trên một hòn đảo bất kì thuộc quốc gia ~t~. Nếu không có hòn đảo nào thuộc quốc gia ~t~ thì mức thuế bạn phải trả là 0.

Yêu cầu: Với mỗi sự kiện loại 2, in ra mức thuế lớn nhất phải đóng.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~2 \le n \le 200 000, 1 \le q \le 200 000~).
• Dòng thứ hai chứa ~n - 1~ số nguyên ~p_2, p_3, \dots, p_n~ (~1 \le p_i < i~), trong đó ~p_i~ có nghĩa là có một tuyến đường biển giữa hòn đảo ~i~ và hòn đảo ~p_i~.
• Dòng thứ ba chứa ~n~ số nguyên ~t_1, t_2, \dots, t_n~ (~1 \le t_i \le n~), trong đó hòn đảo ~i~ thuộc địa phận của quốc gia ~t_i~.
• Dòng thứ tư chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ (~1 \le c_i \le 10^9~) là mức thuế tương ứng của từng quốc gia.
• ~q~ dòng tiếp theo, mỗi dòng bắt đầu bằng số nguyên ~x_i~ (~1 \le x_i \le 2~) là loại truy vấn:
  • Nếu ~x_i = 1~, tiếp theo là hai số nguyên ~v~ và ~t_{new}~ (~1 \le v, t_{new} \le n~).
  • Nếu ~x_i = 2~, tiếp theo là hai số nguyên ~t~ và ~k~, sau đó là ~k~ số nguyên ~a_1, a_2, \dots, a_k~ (~1 \le t, k, a_i \le n~).

Output

• Với mỗi sự kiện loại 2, in ra trên một dòng mức thuế lớn nhất mà bạn phải đóng. Nếu không có hòn đảo nào thỏa mãn thì in ra 0.