Query Format

• startIndex is the zero-based index at which purchasing must begin.
• budget is the maximum total amount that may be spent.

Buying Rules

• Buying must begin at startIndex.
• Products must be purchased consecutively from left to right.
• The total price of all purchased products must not exceed budget.
• A product cannot be skipped to purchase a later product.
• If the first available product costs more than the budget, the answer for that query is 0.

Method Signature

• prices contains the product prices in non-decreasing order.
• queries contains queries in the format "startIndex,budget".
• The returned list contains one answer for each query in the same order as the queries.

Constraints

• 1 ≤ prices.size() ≤ 100,000
• 1 ≤ prices.get(i) ≤ 1,000,000,000
• prices.get(i) ≤ prices.get(i + 1) for every valid i
• 1 ≤ queries.size() ≤ 100,000
• Each query has the format "startIndex,budget".
• 0 ≤ startIndex < prices.size()
• 0 ≤ budget ≤ 1,000,000,000,000,000
• The sum of purchased product prices should be calculated using a 64-bit integer type.

Examples

Example 1

• For "0,11", the prices 2 + 4 + 5 = 11, so 3 products can be purchased.
• For "1,17", the prices 4 + 5 + 8 = 17, so 3 products can be purchased.
• For "3,7", the first available product costs 8, so no product can be purchased.

Example 2

• Starting at index 2, the prices 3 + 6 = 9 fit, but adding 9 exceeds the budget.
• Starting at index 4, the prices 9 + 12 = 21 fit within the budget.
• Starting at index 5, the single product priced at 12 can be purchased.
• A budget of 0 cannot purchase any product.