Sliding GCD

Problem Statement

For the set S of natural numbers, let f (S) be the number of elements in the set \\ {GCD (T) | T ⊆ S, T is not empty \\}.

Here, GCD (T) is the greatest integer that divides all the numbers contained in T.
In particular, note that GCD (\\ {a \\}) = a when T consists of only one integer a.

Find f (\\ {i, i + 1, ..., i + W --1 \\}) for i = 1, 2, ..., N --W + 1.

Constraints

* 1 ≤ W ≤ N ≤ 10 ^ 5

Input

Input follows the following format. All given numbers are integers.


N W

Output

The value of f (\\ {i, i + 1, ..., i + W-1 \\}) when i = 1, 2, ..., N-W + 1 is separated by a space. Print on a line.

Examples

Input

10 2


Output

2 3 3 3 3 3 3 3 3


Input

30 7


Output

7 8 9 10 10 11 11 11 11 12 11 12 10 12 12 11 10 12 12 12 10 11 11 13
#include <set>
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <sstream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <map>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int cnt[100010];

set<int> divisor(int N){
  set<int> res;
  for(int i=1;i*i<=N;i++){
    if(N%i==0){
      res.insert(i);
      res.insert(N/i);
    }
  }
  return res;
}

int main(){
  // ifstream cin("in.txt");
  int N,W;
  cin>>N>>W;
  int ans=0;
  // [1,W]の値について、約数を計算
  for(int i=1;i<=W;i++){
    set<int> s=divisor(i);
    for(set<int>::iterator it=s.begin();it!=s.end();it++){
      int num=*it;
      cnt[num]++;
      // 今回入ってきた数字は無条件に増える
      if(num==i)ans++;
      else{
        if(!(1<=num&&num<=i)&&cnt[num]==2)ans++;
      }
    }
  }
  cout<<ans;
  for(int i=0;i<N-W;i++){
    // for(int j=0;j<10;j++)
    //   cout<<cnt[j]<<" ";cout<<endl;
    {
      set<int> s=divisor(W+i+1);
      for(set<int>::iterator it=s.begin();it!=s.end();it++){
        int num=*it;
        cnt[num]++;
        if(num==W+i+1)ans++;
        else if(!(i+1<=num&&num<=W+i+1)&&cnt[num]==2)ans++;
      }
    }
    {
      set<int> s=divisor(i+1);
      for(set<int>::iterator it=s.begin();it!=s.end();it++){
        int num=*it;
        cnt[num]--;
        // 今回出て行った数字が維持できるかどうか
        if(num==i+1){
          if(cnt[num]<2)ans--;
        }
        // そうでない場合
        else{
          if(cnt[num]==1)ans--;
        }
      }
    }
    cout<<" "<<ans;
  }
  cout<<endl;
  
  return 0;
}