TRICKS

Just Update and Print the array(sqrt decompossion) (update array m time each time index will be ax+b where x= start from 1 to some value k such than ax+b<=n) and print array

Just Update and Print the array

You are given a 1-indexed array of size N. Initially, all elements of the array are zeros. You need to performU updates to the array.

Each Update asks you to add 1 to the elements of the array at the indices specified by 'ax+b' for all non-negative integers x, where a and b are positive integers which specify an update query.

After performing all the updates to the array, print the array with every entry separated by space.

Input

First Line of the input contains 2 space separated integers N, U.

Each of the next U lines contains 2 space-separated integers: a and b, specifying an update.

Output

Output the array in a single line after all updates.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ a, b ≤ N
• 1 ≤ U ≤ 2*10⁵

Example

Input:
7 4
1 3
7 7
7 3
2 2

Output:
0 1 2 2 1 2 2

Explanation

Array after first update : [0,0,1,1,1,1,1]

Array after second update : [0,0,1,1,1,1,2]

Array after third update : [0,0,2,1,1,1,2]

Array after fourth update : [0,1,2,2,1,2,2]

=====================================EDITORIAL=========================================

DIFFICULTY:

Medium

PREREQUISITES:

sqrt decomposition, offline range sums

PROBLEM:

Given an array [A1,…,AN]$[A_1,\dots ,A_N]$, all initially zeros. You need to perform U$U$ updates to the array, where each update asks you to increment the array at the indices ax+b$ax+b$ for all integers x≥0$x\ge 0$. What is the resulting array?

QUICK EXPLANATION:

Perform all updates where a>U√$a>\sqrt{U}$ manually. Store all other updates (i.e. those with a≤U√$a\le \sqrt{U}$).

Let's fix an a≤U√$a\le \sqrt{U}$ and perform all updates with this a$a$ simultaneously. To do so:

• Compute [C1,…,CN]$[C_1,\dots ,C_N]$, where Ci$C_i$ is the number of updates (a,b)$(a,b)$ with b=i$b=i$.
• Compute [D1,…,DN]$[D_1,\dots ,D_N]$ where Di=Ci+Di−a$D_i=C_i+D_{i-a}$ for i>a$i>a$ and Di=Ci$D_i=C_i$ for i≤a$i\le a$.
• Finally, increment Ai$A_i$ with Di$D_i$ for all i$i$.

EXPLANATION:

Obviously, brute-force will not work because the worst case complexity of each update is O(N)$O(N)$, so the overall worst-case running time becomes O(UN)$O(UN)$.

The problem is a lot easier though if the updates all have a=1$a=1$. In that case, we're only dealing with range sum updates, which are famously easy to solve with a segment tree. In fact, we don't need a segment tree at all! A much simpler algorithm exists for the offline version of the problem, where it is assumed that all updates are known beforehand:

• Compute [C1,…,CN]$[C_1,\dots ,C_N]$, where Ci$C_i$ is the number of updates (1,b)$(1,b)$ with b=i$b=i$. This can be done with a linear scan among all updates (1,b)$(1,b)$.
• Compute [D1,…,DN]$[D_1,\dots ,D_N]$, where Di$D_i$ is the amount to increment to Ai$A_i$. Di$D_i$ is easily seen to be C1+C2+C3+⋯+Ci$C_1+C_2+C_3+\cdots +C_i$, so Di$D_i$ can easily be calculated using the recurrence Di=Ci+Di−1$D_i=C_i+D_{i-1}$ for i≥1$i\ge 1$ with base case Di=0$D_i=0$ for i<1$i<1$.
• Finally, increment Ai$A_i$ with Di$D_i$ for all i$i$.

For example, suppose N=11$N=11$ and we want to process the queries (1,2)$(1,2)$, (1,5)$(1,5)$, (1,6)$(1,6)$, (1,8)$(1,8)$, (1,8)$(1,8)$ and (1,10)$(1,10)$. We will have:

C=[0,1,0,0,1,1,0,2,0,1,0]$$C=[0,1,0,0,1,1,0,2,0,1,0]$$

D=[0,1,1,1,2,3,3,5,5,6,6]$$D=[0,1,1,1,2,3,3,5,5,6,6]$$

One can check that Di$D_i$ is indeed the value to be added to Ai$A_i$ for all i$i$, and that Di=Ci+Di−1$D_i=C_i+D_{i-1}$ for i≥1$i\ge 1$.

Now, what about the updates a>1$a>1$? Well, we don't know yet. But, we can in fact use a similar algorithm as above for the case a=2$a=2$: there are two types of updates of the form (2,b)$(2,b)$ — those with even b$b$ and and odd b$b$ — and we can use the algorithm above separately for the even and odd ones. And in fact, we can combine both the even and odd half into a single unified algorithm: Just replace the recurrence Di=Ci+Di−1$D_i=C_i+D_{i-1}$ with Di=Ci+Di−2$D_i=C_i+D_{i-2}$. The running time is still O(N)$O(N)$ overall.

Actually, we can perform a similar algorithm for all the other a$a$s! Each particular a$a$ takes O(N)$O(N)$ to process. So we now have an alternative algorithm: group the updates (a,b)$(a,b)$ according to a$a$, then perform the algorithm above for every a$a$. Unfortunately, this algorithm is also slow. Each time we perform the algorithm above we incur a running time of O(N)$O(N)$, giving an overall running time of O(U+N2)$O(U+N^2)$, which is still too slow.

But what if we only perform the algorithm above for some a$a$s? For updates with other a$a$s, we can simply perform the update manually. Let's say we perform the algorithm above only for small a$a$, i.e. those that are ≤s$\le s$ for some (still unknown) value s$s$. Since we perform the algorithm above only s$s$ times, and the running time of all other updates is at worst O(N/s)$O(N/s)$, this gives us an overall running time of O(UN/s+Ns)$O(UN/s+Ns)$. If we choose s$s$ as, say, Θ(N−−√)$\mathrm{\Theta }(\sqrt{N})$, then the overall algorithm becomes O((U+N)N−−√)$O((U+N)\sqrt{N})$, which is fast enough to pass the time limit!

Keep in mind though that you have a choice of constant in the "Θ$\mathrm{\Theta }$ notation" so practically it's still up to you to choose s$s$really. The optimal constant depends on your implementation and you can try to find it via trial-and-error / ternary search. We suggest choosing s$s$ not too far from N−−√$\sqrt{N}$ though.

Theoretically better parameter

Notice above that we chose s$s$ as Θ(N−−√)$\mathrm{\Theta }(\sqrt{N})$ without really thinking about it that much. It's just pure intuition. Here we'll choose a better parameter to get a theoretically better running time.

The running time is O(UN/s+Ns)$O(UN/s+Ns)$, and we want to make the running time as small as possible. Since UN/s$UN/s$decreases and Ns$Ns$ decreases as s$s$ increases, it's best to choose s$s$ that will make them equal to make their sum as small as possible (at least in terms of O$O$ notation). Thus, we want UN/s=Ns$UN/s=Ns$. Thus, in fact the better choice would be s=Θ(U√)$s=\mathrm{\Theta }(\sqrt{U})$, NOT Θ(N−−√)$\mathrm{\Theta }(\sqrt{N})$, and the running time we get O(U+NU√)$O(U+N\sqrt{U})$. Note that this running time is better than O((U+N)U√)$O((U+N)\sqrt{U})$ in almost all cases!

Note that we said O(U+NU√)$O(U+N\sqrt{U})$ and not just O(NU√)$O(N\sqrt{U})$, because it's possible that U>N2$U>N^2$, in which case iterating through all updates dominates the running time.

This doesn't really matter that much in terms of the contest, but it's interesting nonetheless.

Time Complexity:

O(U+NU√)$O(U+N\sqrt{U})$ or O((U+N)N−−√)

=======================================CODE===========================================

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> p;

#define getcx getchar_unlocked

inline void inp( int &n )//fast input function

{

   n=0;

   int ch=getcx();int sign=1;

   while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}

   while(  ch >= '0' && ch <= '9' )

           n = (n<<3)+(n<<1) + ch-'0', ch=getcx();

   n=n*sign;

}

int ans[100005],n,u;

p arr[200005];

void update2(int st,int ct)

{

    int i,x;

    int a=arr[st].first;

    for(i=0;i<ct;i++,st++)

    {

        int b=arr[st].second;

        for(x=0;a*x+b<=n;x++)

        {

            ans[a*x+b]++;

        }

    }

}

void update1(int st,int ct)

{

    int i,j;

    //  creating C[] and D[] array as   mentioned in editoral..

    int c[n+1];

    int d[n+1];

    int a=arr[st].first;

    memset(c,0,sizeof(c));

    memset(d,0,sizeof(d));

    for(i=st;i<st+ct;i++)

    {

        c[arr[i].second]++;

    }

    for(i=1;i<=a;i++)

        d[i]=c[i];

    for(;i<=n;i++)

        d[i]=c[i]+d[i-a];

    for(i=1;i<=n;i++)// updating 

        ans[i]+=d[i];

}

int main()

{

    ios_base::sync_with_stdio(false);

    int i,j,k;

    inp(n);inp(u);

    for(i=0;i<u;i++)

    {

        inp(arr[i].first);

   inp(arr[i].second);

    }

    sort(arr,arr+u);

    i=0;

    int sq=int(sqrt(n));

    while(i<u)

    {

        int count=1;

        while(arr[i].first==arr[i+1].first)

        {

            count++;

            i++;

        }

        int tempa=arr[i].first;

        if(tempa<=sq)

            update1(i-count+1,count);

        else

            update2(i-count+1,count);

        i++;

    }

    for(i=1;i<=n;i++)

        cout<<ans[i]<<" ";

}