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 <bits/stdc++.h>

#define ll long long
#define llong long long
#define REP(i,n) for(auto i=0;i<n;++i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define ALL(v) v.begin(),v.end()
#define pb push_back

using namespace std;

//約数が現在の範囲で何個あるか
int divisor[100001];

//その値が範囲内に2個以上あるか
bool is_used[100001] = {};

//現在の範囲で2個以上あるものの総数
int num;


//値xの約数について、範囲に追加
void plus_divisor(int x){
  
  divisor[x]++;
  
  for(int i = 1; i * i <= x; ++i){
    if(x % i == 0){
      divisor[i]++; 
      if(i * i != x) divisor[x / i]++;
      if(divisor[i] >= 2 && !is_used[i]){
        num++;
        is_used[i] = true;
      }
      if(divisor[x / i] >= 2 && !is_used[x / i]){
        num++;
        is_used[x / i] = true;
      }
    }
  }
}

//値xの約数について、範囲から削除
void minus_divisor(int x){

  
  divisor[x]--;
  
  for(int i = 1; i * i <= x; ++i){
    if(x % i == 0){
      divisor[i]--; 
      if(i * i != x) divisor[x / i]--;
      if(divisor[i] < 2 && is_used[i]){
        num--;
        is_used[i] = false;
      }
      if(divisor[x / i] < 2 && is_used[x / i]){
        num--;
        is_used[x / i] = false;
      }
    }
  }
}

int main(){

  int n, w;
  cin >> n >> w;
  
  for(int i = 1; i <= w; ++i){
    plus_divisor(i);
  }

  for(int i = 1; i <= n - w + 1; ++i){
    cout << num;
    if(i != n - w + 1){
      minus_divisor(i); plus_divisor(i+w);
      cout << " ";
    }else{
      cout << "\n";
    }
  }

  return 0;
}


