Cho đồ thị hàm số gồm \(N\) đỉnh được đánh số từ \(0\) đến \(N-1\). Mỗi đỉnh \(i\) có đúng một cung đi ra hướng tới \(next[i]\) và cung này có trọng số (chi phí) là \(W_i\).

Bạn cần xử lý \(Q\) truy vấn: Xuất phát từ đỉnh \(U\), sau khi đi liên tiếp đúng \(K\) bước, trọng số nhỏ nhất trong số các cung đã đi qua là bao nhiêu?

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên đại diện cho mảng \(next\) (\(0 \le next[i] < N\)).
• Dòng ba chứa \(N\) số nguyên dương \(W_0, W_1, \dots, W_{N-1}\) (\(1 \le W_i \le 10^{18}\)) là trọng số các cung.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(U\) và \(K\) (\(0 \le U < N, 1 \le K \le 10^{18}\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra trọng số cung nhỏ nhất trên một dòng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000, K \le 1000\).
• Subtask 2 (30% số điểm): \(K \le 10^9\).
• Subtask 3 (40% số điểm): \(N, Q \le 10^5, K \le 10^{18}\), các ràng buộc gốc.

Ví dụ

Input:

5 3
2 0 1 3 4
10 20 30 40 50
0 3
1 4
3 10

Output:

10
10
40

Giải thích:

• Cung đi ra: \(0 \to 2\) (nặng 10), \(1 \to 0\) (nặng 20), \(2 \to 1\) (nặng 30), \(3 \to 3\) (nặng 40), \(4 \to 4\) (nặng 50).
• Truy vấn 1: Đi từ \(0 \to 2 \to 1 \to 0\) có các cung trọng số \(\{10, 30, 20\} \to\) nhỏ nhất là 10.
• Truy vấn 2: Đi từ \(1 \to 0 \to 2 \to 1 \to 0\) có các cung trọng số \(\{20, 10, 30, 20\} \to\) nhỏ nhất là 10.
• Truy vấn 3: Đi từ \(3 \to 3 \to \dots \to 3\) có các cung \(\{40, 40, \dots\} \to\) nhỏ nhất là 40.