Truy vấn dãy con dài nhất

Trong một buổi thực hành, FullHouse Dev đang nghiên cứu về các thuật toán xử lý dãy số. Họ được giao một bài toán thú vị về việc tìm dãy con có tổng nhỏ hơn một giá trị cho trước.

Bài toán

FullHouse Dev được cung cấp một mảng số nguyên dương \(A\) có độ dài \(n\) và \(q\) truy vấn. Trong mỗi truy vấn, với một số nguyên dương \(K\) cho trước, họ cần tìm độ dài của dãy con dài nhất có tổng các phần tử nhỏ hơn \(K\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Dòng đầu tiên của mỗi test case chứa hai số nguyên \(n\) và \(q\) - độ dài của mảng \(A\) và số lượng truy vấn.
• Dòng thứ hai của mỗi test case chứa \(n\) số nguyên dương - các phần tử của mảng \(A\).
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(K\) cho mỗi truy vấn tương ứng.

OUTPUT FORMAT:

• Với mỗi truy vấn trong test case, in ra độ dài của dãy con dài nhất có tổng các phần tử nhỏ hơn \(K\) trên một dòng mới.

Ràng buộc:

• \(1 \leq n, q \leq 10^5\)
• Tổng của \(n\) và tổng của \(q\) qua tất cả các test case không vượt quá \(10^5\)

Ví dụ

INPUT

1
3 3
5 7 2
8
2
20

OUTPUT

2
0
3

Giải thích

• Với truy vấn đầu tiên \(K = 8\), độ dài lớn nhất là 2 với dãy con [5, 2].
• Với truy vấn thứ hai \(K = 2\), không có dãy con nào có tổng nhỏ hơn 2.
• Với truy vấn thứ ba \(K = 20\), độ dài lớn nhất là 3 với dãy con [5, 7, 2].