Biến Đổi Trên Cây

Minh Anh được mời để đưa ra một bài toán khó cho cuộc thi "coding ao làng" vừa được tổ chức gần đây. Phân vân với những ý tưởng của mình, cô ấy đang cân nhắc sử dụng bài toán sau.

Bạn được cho một cây không trọng số gồm \(N\) đỉnh, với gốc là đỉnh \(1\). Mỗi đỉnh \(i\) có một giá trị \(v_i\) đi kèm. Cấu trúc cây được mô tả bởi mảng \(p_1, p_2, \dots, p_{N-1}\), trong đó \(p_i\) là cha của đỉnh \(i+1\).

Một hàm \(f(y)\) được định nghĩa cho một đỉnh \(y\) trong cây như sau:

trong đó \(d(x, y)\) là khoảng cách giữa hai đỉnh \(x\) và \(y\), còn \(S_y\) là tập các đỉnh mà \(y\) là tổ tiên của chúng.

Bạn được cho \(Q\) truy vấn, mỗi truy vấn gồm hai đỉnh \(x\) và \(y\). Với mỗi truy vấn, cần mô phỏng các thao tác sau trên cây và tính giá trị \(f(y)\):

• Gắn tất cả các đỉnh mà cha của chúng là \(x\) sang cha của \(x\).
• Loại bỏ \(x\) khỏi cây.
• Chèn lại đỉnh \(x\) vào cây, giữa \(y\) và một hậu duệ của \(y\) thuộc cây con trước đó chứa \(x\).

Nếu \(y\) là cha của \(x\), cấu trúc cây không thay đổi. Luôn đảm bảo \(x\) thuộc cây con của \(y\). Sau mỗi truy vấn, giá trị \(f(y)\) được tính trên cây đã tạm thời thay đổi, sau đó cây trở về trạng thái ban đầu.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 5 \cdot 10^5\)) --- số đỉnh của cây và số truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên \(v_1, v_2, \dots, v_N\) (\(1 \le v_i \le 10^6\)) --- giá trị của từng đỉnh.
• Dòng thứ ba chứa \(N-1\) số nguyên \(p_1, p_2, \dots, p_{N-1}\) (\(1 \le p_i \le i\)) --- \(p_i\) là cha của đỉnh \(i+1\).
• Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\) (\(1 \le x, y \le N\)) --- các đỉnh liên quan đến thao tác đã mô tả.

Output

• In ra \(Q\) dòng, mỗi dòng là giá trị của hàm \(f(y)\) trên cây sau khi thực hiện thao tác của truy vấn tương ứng.

Example

3 1
1 2 3
1 2
3 1

7

3 2
4 5 6
1 1
2 1
3 1

11
11

5 3
2 5 2 2 2
1 2 3 2
4 3
3 2
5 1

2
8
26

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 21 & \(1 \le N, Q \le 1000\)

2 & 27 & Cây là một dây chuyền, \(p_i = i\) với mọi \(i\) từ \(1\) đến \(N-1\)

3 & 22 & Mỗi đỉnh là cha của nhiều nhất \(20\) đỉnh con

4 & 30 & Không có ràng buộc bổ sung

\hline
\endtabular