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
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

// 2013/03/17
public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-12;

	int n, w;

	void run(){
		n=sc.nextInt();
		w=sc.nextInt();
		solve();
	}

	@SuppressWarnings("unchecked")
	void solve(){
		ArrayList<Integer>[] div=new ArrayList[n+2];
		for(int i=0; i<div.length; i++){
			div[i]=new ArrayList<Integer>();
		}
		for(int i=1; i<=w; i++){
			for(int j=i; j<=n; j+=i){
				div[j].add(i);
			}
		}
		int[] count=new int[n+1];
		for(int i=1; i<=w; i++){
			for(int d : div[i]){
				count[d]++;
			}
		}
		int sum=w;
		for(int i=1; i<=n-w+1; i++){
			print(sum+(i<n-w+1?" ":"\n"));
			// iを消すかも
			if(count[i]<2){ // i
				sum--;
			}
			for(int d : div[i]){
				if(--count[d]==1){
					sum--;
				}
			}
			sum++; // count[i+w] = 0
			for(int d : div[i+w]){
				if(++count[d]==2&&d<=i){
					sum++;
				}
			}
		}
	}

	boolean[] flag;
	int[] count;
	int sum, left, right;

	void solve_(){
		flag=new boolean[n+1];
		count=new int[n+1];
		sum=0;
		left=1;
		right=w+1;
		for(int i=1; i<w; i++){
			for(int k=1; k*k<=i; k++){
				if(i%k==0){
					count[k]++;
					update(k);
					if(i/k!=k){
						count[i/k]++;
						update(i/k);
					}
				}
			}
		}
		for(int i=0; i<n-w+1; i++){
			left=i+1;
			right=i+w+1;
			for(int k=1; k*k<=i; k++){
				if(i%k==0){
					count[k]--;
					update(k);
					if(i/k!=k){
						count[i/k]--;
						update(i/k);
					}
				}
			}
			for(int k=1; k*k<=i+w; k++){
				if((i+w)%k==0){
					count[k]++;
					update(k);
					if((i+w)/k!=k){
						count[(i+w)/k]++;
						update((i+w)/k);
					}
				}
			}
			update(left-1);
			update(right-1);
			// debug("i", i, "i+w-1", i+w-1);
			// debug("count", count);
			// debug("flag", flag);
			// debug("sum", sum);
			// debug(sum);
			// debug();
			print(sum+(i<n-w?" ":"\n"));
		}
		// iの約数が減って
		// i+wの約数が増える
		// iが確定じゃなくなった
		// i+wが確定する
	}

	void update(int i){
		boolean det=left<=i&&i<right;
		if(flag[i]&&!det&&count[i]<2){
			flag[i]=false;
			sum--;
		}
		if(!flag[i]&&(det||count[i]>=2)){
			flag[i]=true;
			sum++;
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
		System.out.flush();
	}
}