Real problems.
Your next challenge.

Problem summary

An M-hour clock displays numbers 0 through M−1. Clock i starts at bi and displays ai successive hourly readings, including the initial reading, then stops. For each queried hour t, sum how many times all clocks display t before stopping.

Constraints

1 ≤ N,Q ≤ 200000; 1 ≤ M ≤ 10^9; 1 ≤ ai ≤ 10^12; 0 ≤ bi,ti < M.

Worked example

An independently prepared example for this explanation.

2 5
7 4
2 0
3
0
2
4

3
1
2

Solution analysis

1. Each full cycle contributes floor(ai/M) to every query; accumulate these in a common base.
2. The remaining ai mod M readings form a circular interval beginning at bi. Split a wrapping interval at zero and encode each ordinary half-open interval with +1 at its beginning and −1 at its end.
3. Sort events, combine equal coordinates, and store prefix event sums. For each query use upper_bound to retrieve its interval coverage, then add the base.

Why it works

Full cycles account for an equal number of every hour. The remainder visits each hour of its circular interval once. Difference events count exactly the clocks whose remainder includes a query.

Watch out. The initial reading counts, so a remainder of length r covers [b,b+r), not an interval of length r+1. Use 64-bit totals.

An independently written complete program with standard headers.

// Key idea: Full cycles account for an equal number of every hour. The remainder visits each hour of
// its circular interval once.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin>>n>>m;
    vector<pair<long long,long long>>e;
    long long base=0;
    auto interval=[&](long long l,long long r){
        if(l<r){
            e.push_back({l,1});
            e.push_back({r,-1});
        }
    };
    while(n--){
        long long a,b;
        cin>>a>>b;
        base+=a/m;
        long long len=a%m;
        interval(b,min(m,b+len));
        if(b+len>m){
            interval(0,b+len-m);
        }
    }
    sort(e.begin(),e.end());
    vector<long long>x,s;
    long long running=0;
    for(size_t i=0;i<e.size();){
        auto at=e[i].first;
        while(i<e.size()&&e[i].first==at){
            running+=e[i++].second;
        }
        x.push_back(at);
        s.push_back(running);
    }
    int q;
    cin>>q;
    while(q--){
        long long t;
        cin>>t;
        int j=upper_bound(x.begin(),x.end(),t)-x.begin();
        cout<<base+(j?s[j-1]:0)<<'\n';
    }
}