Hạo quyết định tạo một bài toán cho Ngân (và Luân). Vì anh ấy không thích trẻ con, anh quyết định làm bài toán khó nhất có thể. Anh nghĩ ra một bài toán phức tạp liên quan đến một cây liên tục thay đổi, chỉ để làm cho thí sinh phải chịu đựng càng nhiều càng tốt.

Bạn được cho một cây không có trọng số với \(N\) nút, trong đó gốc của cây là nút \(1\). Mỗi nút có một giá trị liên quan \(v[i]\). Cấu trúc của cây được xác định bằng một mảng \(p[i]\), trong đó với mỗi \(i\) từ \(1\) đến \(N - 1\), \(p[i]\) biểu thị cha của \(i + 1\).

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

\[f(y) = Σ(x∈Sy) d(x, y) · v[x]\]

trong đó \(d(x, y)\) biểu thị khoảng cách giữa các nút \(x\) và \(y\), trong khi Sy chứa tất cả các nút mà \(y\) là tổ tiên.

Bạn được cho \(Q\) truy vấn với hai nút \(x\) và \(y\). Với mỗi truy vấn, phép biến đổi sau phải được mô phỏng trong cây và hàm \(f(y)\) cần được tính toán:

1. Gắn tất cả các nút mà \(x\) là cha vào cha của \(x\)
2. Loại bỏ \(x\) khỏi cây
3. Chèn nút \(x\) trở lại cây, giữa \(y\) và con cháu của \(y\) mà từ cây con đó \(x\) đã bị loại bỏ.

Nếu \(y\) là cha của \(x\), cây vẫn không thay đổi. Luôn đúng rằng \(x\) nằm trong cây con của \(y\). Với mỗi truy vấn, giá trị của \(f(y)\) phải được tính toán sau khi cây được sửa đổi tạm thời theo quy trình được mô tả ở trên. Các sửa đổi cây không phải là vĩnh viễn, tức là sau mỗi truy vấn, cây trở về trạng thái ban đầu.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) \((1 \le N, Q \le 5 \times 10^5)\), lần lượt là số nút trong cây và số truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên \(v[i]\) \((1 \le v[i] \le 10^6)\), đại diện cho giá trị của mỗi nút.
• Dòng thứ ba chứa \(N - 1\) số nguyên \(p[i]\) \((1 \le p[i] \le i)\), trong đó \(p[i]\) biểu thị cha của nút \(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)\), biểu thị các nút liên quan đến thao tác được mô tả ở trên.

Đầu ra

• Trong \(Q\) dòng tiếp theo xuất giá trị của hàm \(f(y)\) trên cây đã sửa đổi.

Chấm điểm

Input 1

3 1
1 2 3
1 2
3 1

Output 1

7

Input 2

3 2
4 5 6
1 1
2 1
3 1

Output 2

11
11

Input 3

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

Output 3

2
8
26

Làm rõ ví dụ đầu tiên: Sau khi áp dụng thao tác trên cây, nút 3 ở khoảng cách 1 từ nút 1 và nút 2 ở khoảng cách 2 từ nút 1. Kết quả là 3 + 2 · 2 = 7.