Hello everyone This problem was one of the problems in the ECPC qualifications, and I couldn't think of an efficient way to solve it.

We are given an array a of n integer, and an integer k. Next, we will have q queries, each query has L R. We need to answer the following question for each query: How many subarrays in the range L to R (inclusive) where sum of each subarray is equal to K?

To be honset I couldn't find a good solution to this problem. So I would appreciate your help.

Input: 10 5 2 3 0 0 0 2 3 1 1 0 7 1 2 1 3 1 7 1 10 2 7 2 6 3 8

Output: 1 2 9 11 5 1 4