Problem: Numbers k-bonacci (k is integer, k > 1) are a generalization of Fibonacci numbers and are determined as follows:

  * F(k, n) = 0, for integer n, 1 ≤ n < k; 
  * F(k, k) = 1; 
  * F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k), for integer n, n > k. 



Note that we determine the k-bonacci numbers, F(k, n), only for integer values of n and k.

You've got a number s, represent it as a sum of several (at least two) distinct k-bonacci numbers. 

Input

The first line contains two integers s and k (1 ≤ s, k ≤ 109; k > 1).

Output

In the first line print an integer m (m ≥ 2) that shows how many numbers are in the found representation. In the second line print m distinct integers a1, a2, ..., am. Each printed integer should be a k-bonacci number. The sum of printed integers must equal s.

It is guaranteed that the answer exists. If there are several possible answers, print any of them.

Examples

Input

5 2


Output

3
0 2 3


Input

21 5


Output

3
4 1 16

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class B {

	final int MOD = 1000000007;
	final double eps = 1e-12;
	final int INF = (int)1e9;
	
	public B () throws IOException {
		long S = sc.nextLong();
		long K = sc.nextLong();		
		start();
		
		long [] F = new long [1000000];
		long [] G = new long [1000000];
		F[0] = 1; G[0] = 1;
		System.err.println(K + " " + S);
		for (int i = 1; i < 1000000; ++i) {
			F[i] = G[i-1];
			G[i] = G[i-1] + F[i];
			if (i >= K)
				G[i] -= F[i-(int)K];
			if (F[i] > S)
				break;
		}
		
		List<Long> R = new ArrayList<Long>();
		R.add(0L);
		for (int i = 999999; i >= 0; --i)
			if (F[i] > 0 && S >= F[i]) {
				S -= F[i];
				R.add(F[i]);
			}
		
		print(R.size());
		StringBuilder B = new StringBuilder();
		for (Long r : R)
			B.append(" ").append(r);
		print(B.toString().trim());
		pw.flush();
		System.out.flush();
	}

	////////////////////////////////////////////////////////////////////////////////////
	
	void NO() {
		throw new Error("NO!");
	}
	
	static MyScanner sc;
	
	static class MyScanner {
		String next() throws IOException {
			newLine();
			return line[index++];
		}
		
		char nextChar() throws IOException {
			return next().charAt(0);
		}
				
		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		
		long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		
		double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		
		String nextLine() throws IOException {
			line = null;
			return r.readLine();
		}
		
		String [] nextStrings() throws IOException {
			line = null;
			return r.readLine().split(" ");
		}
		
		char [] nextChars() throws IOException {
			return next().toCharArray();
		}

		int [] nextInts() throws IOException {
			String [] L = nextStrings();
			int [] res = new int [L.length];
			for (int i = 0; i < L.length; ++i)
				res[i] = Integer.parseInt(L[i]);
			return res;
		}	
		
		long [] nextLongs() throws IOException {
			String [] L = nextStrings();
			long [] res = new long [L.length];
			for (int i = 0; i < L.length; ++i)
				res[i] = Long.parseLong(L[i]);
			return res;
		}

		double [] nextDoubles() throws IOException {
			String [] L = nextStrings();
			double [] res = new double [L.length];
			for (int i = 0; i < L.length; ++i)
				res[i] = Double.parseDouble(L[i]);
			return res;
		}

		boolean eol() {
			return index == line.length;
		}

		//////////////////////////////////////////////
		
		private final BufferedReader r;

		MyScanner () throws IOException {
			this(new BufferedReader(new InputStreamReader(System.in)));
		}
		
		MyScanner(BufferedReader r) throws IOException { 
			this.r = r;
		}
		
		private String [] line;
		private int index;

		private void newLine() throws IOException {
			if (line == null || eol()) {
				line = r.readLine().split(" ");
				index = 0;
			}
		}		
	}
	
	static PrintWriter pw = new PrintWriter(System.out);
	
	static void print (Object... a) {
		StringBuilder b = new StringBuilder();
		for (Object o : a)
			b.append(" ").append(o);
		pw.println(b.toString().trim());
	}

	static void exit (Object... a) {
		print(a);
		exit();
	}

	static void exit () {
		pw.flush();
		System.err.println("------------------");
		System.err.println("Time: " + secs());
		System.exit(0);
	}
	
	////////////////////////////////////////////////////////////////////////////////////
	
	public static void main(String[] args) throws IOException {
		run();
		exit();
	}

	static void start() {
		t = millis();
	}

	static void run () throws IOException {
		sc = new MyScanner ();
		new B();
	}

	static long t;
	
	static long millis() {
		return System.currentTimeMillis();
	}	

	static double secs() {
		return (millis() - t) / 1000.0;
	}
}