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\), ta có thể đi tối đa bao nhiêu bước liên tiếp sao cho tổng trọng số của các cung đi qua không vượt quá \(S\)?

Đị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^9\)) 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à \(S\) (\(0 \le U < N, 0 \le S \le 10^{18}\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số bước đi tối đa trên một dòng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000, S \le 10^9\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5, S \le 10^{18}\).

Ví dụ

Input:

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

Output:

1
2
0

Giải thích:

• Các cung: \(0 \to 2\) (nặng 10), \(2 \to 1\) (nặng 30), \(1 \to 0\) (nặng 20), \(3 \to 3\) (nặng 40), \(4 \to 4\) (nặng 50).
• Truy vấn 1 (\(U=0, S=25\)):
  • Đi 1 bước (\(0 \to 2\)): tổng nặng 10 \(\le 25\).
  • Đi 2 bước (\(0 \to 2 \to 1\)): tổng nặng \(10 + 30 = 40 > 25\). \(\to\) Tối đa đi được 1 bước.
• Truy vấn 2 (\(U=1, S=55\)):
  • Đi 1 bước (\(1 \to 0\)): tổng 20.
  • Đi 2 bước (\(1 \to 0 \to 2\)): tổng \(20 + 10 = 30\).
  • Đi 3 bước (\(1 \to 0 \to 2 \to 1\)): tổng \(30 + 30 = 60 > 55\). \(\to\) Tối đa đi được 2 bước.
• Truy vấn 3 (\(U=3, S=30\)): Cung duy nhất đi ra từ 3 nặng 40 \(> 30 \to\) đi tối đa 0 bước.