Proficient.
Put your skills to the test.

Problem summary

A day has M hours numbered 0 through M−1. Clock i starts showing b[i] and displays a[i] consecutive hours, advancing one per hour modulo M, then goes blank. For each queried hour t, find the total number of times all clocks display t during their lifetimes.

Constraints

1 ≤ N,Q ≤ 200,000; 1 ≤ M ≤ 10⁹; 1 ≤ a[i] ≤ 10¹²; 0 ≤ b[i],t < M.

Worked example

An independently prepared example for this explanation.

5 7
12 0
5 4
9 6
2 6
14 1
3
0
3
1

8
5
6

Solution analysis

1. Each clock completes a[i]/M full cycles, contributing that many occurrences to every hour. Add these quotients into a common base. Its remaining a[i]%M displays form one circular interval beginning at b[i].
2. Split a wrapping interval into [b[i],M−1] and [0,end−M]; a nonwrapping interval remains [b[i],end]. For each inclusive interval [l,r], create a +1 event at l and a −1 event at r+1. Sort all events and the queries, then sweep in increasing hour order to maintain the number of active remainder intervals.
3. The answer at an hour is base plus the active count after all events at that hour have been processed. In the example the full-cycle base is 1+0+1+0+2=4. Four remainder intervals cover hour 0, one covers hour 3 and two cover hour 1, producing 8,5,6. Restore query order using their original indices.

Why it works

Dividing each lifetime into complete cycles and a remaining consecutive segment accounts for every display exactly once. The interval split preserves exactly the covered residues. Difference events add one at the first covered hour and remove it just after the last; hence the sweep’s active count equals the number of remainders containing each queried hour. Adding the complete-cycle base yields the required total.

Watch out. The first displayed hour counts toward lifetime. Remainder zero adds no interval. Process removal and addition events at a query coordinate before answering it; use 64-bit totals.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
// Algorithm: Each clock completes a[i]/M full cycles, contributing that many occurrences to
// every hour.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long day;
    cin>>n>>day;
    vector<pair<long long,int>>events;
    long long base=0;
    auto interval=[&](long long left,long long right){
        if(left<=right){
            events.push_back({left,1});
            events.push_back({right+1,-1});
        }
    };
    for(int i=0;i<n;++i){
        long long lifetime,start;
        cin>>lifetime>>start;
        base+=lifetime/day;
        long long remainder=lifetime%day;
        if(remainder==0){
            continue;
        }
        long long end=start+remainder-1;
        interval(start,min(end,day-1));
        if(end>=day){
            interval(0,end-day);
        }
    }
    int q;
    cin>>q;
    vector<pair<long long,int>>queries(q);
    for(int i=0;i<q;++i){
        cin>>queries[i].first;
        queries[i].second=i;
    }
    sort(events.begin(),events.end());
    sort(queries.begin(),queries.end());
    vector<long long>answer(q);
    size_t event=0;
    long long active=0;
    for(auto query:queries){
        while(event<events.size()&&events[event].first<=query.first){
            active+=events[event].second;
            ++event;
        }
        answer[query.second]=base+active;
    }
    for(long long value:answer){
        cout<<value<<'\n';
    }
}