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.

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.

Ràng buộc & Subtasks

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