You are given n
 points on the x
 axis, at increasing positive integer coordinates x1<x2<…<xn
.

For each pair (i,j)
 with 1≤i<j≤n
, you draw the segment [xi,xj]
. The segments are closed, i.e., a segment [a,b]
 contains the points a,a+1,…,b
.

You are given q
 queries. In the i
-th query, you are given a positive integer ki
, and you have to determine how many points with integer coordinates are contained in exactly ki
 segments.

Input
Each test contains multiple test cases. The first line contains the number of test cases t
 (1≤t≤104
). The description of the test cases follows.

The first line of each test case contains two integers n
, q
 (2≤n≤105
, 1≤q≤105
) — the number of points and the number of queries.

The second line of each test case contains n
 integers x1,x2,…,xn
 (1≤x1<x2<…<xn≤109
) — the coordinates of the n
 points.

The third line of each test case contains q
 integers k1,k2,…,kq
 (1≤ki≤1018
) — the parameters of the q
 queries.

It is guaranteed that the sum of n
 over all test cases does not exceed 105
, and the sum of q
 over all test cases does not exceed 105
.

Output
For each test case, output a single line with q
 integers: the i
-th integer is the answer to the i
-th query.

Example
InputCopy
3
2 2
101 200
2 1
6 15
1 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 8
254618033 265675151 461318786 557391198 848083778
6 9 15 10 6 9 4 4294967300
OutputCopy
0 100 
0 0 0 0 2 0 0 0 3 0 2 0 0 0 0 
291716045 0 0 0 291716045 0 301749698 0 
Note
In the first example, you only draw the segment [101,200]
. No point is contained in exactly 2
 segments, and the 100
 points 101,102,…,200
 are contained in exactly 1
 segment.

In the second example, you draw 15
 segments: [1,2],[1,3],[1,5],[1,6],[1,7],[2,3],[2,5],[2,6],[2,7],[3,5],[3,6],[3,7],[5,6],[5,7],[6,7]
. Points 1,7
 are contained in exactly 5
 segments; points 2,4,6
 are contained in exactly 9
 segments; points 3,5
 are contained in exactly 11
 segments.


#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;

    vector<long long> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    int block_size = sqrt(n);
    int block_count = (n + block_size - 1) / block_size;
    vector<long long> block_sum(block_count, 0);
    vector<long long> freq(1000001, 0); // Assuming values in x are within 1e6

    // Build block sums
    for (int i = 0; i < n; i++) {
        freq[x[i]]++;
        block_sum[i / block_size] += (x[i] != 0) ? 1 : 0; // Count non-zero values
    }

    // Answer queries
    while (q--) {
        long long k;
        cin >> k;

        long long count = 0;

        // Count complete blocks
        for (int i = 0; i < block_count; i++) {
            if (block_sum[i] >= k) {
                // Count elements in the current block
                int start = i * block_size;
                int end = min(n, start + block_size);
                for (int j = start; j < end; j++) {
                    if (freq[x[j]] == k) count++;
                }
            }
        }

        cout << count << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}


trying sqrt decompositon and diff array