Problem: Gerald has a friend, Pollard. Pollard is interested in lucky tickets (ticket is a sequence of digits). At first he thought that a ticket is lucky if between some its digits we can add arithmetic signs and brackets so that the result obtained by the arithmetic expression was number 100. But he quickly analyzed all such tickets and moved on to a more general question. Now he explores k-lucky tickets.

Pollard sais that a ticket is k-lucky if we can add arithmetic operation signs between its digits to the left or right of them (i.e., "+", "-", " × ") and brackets so as to obtain the correct arithmetic expression whose value would equal k. For example, ticket "224201016" is 1000-lucky as ( - 2 - (2 + 4)) × (2 + 0) + 1016 = 1000.

Pollard was so carried away by the lucky tickets that he signed up for a seminar on lucky tickets and, as far as Gerald knows, Pollard will attend it daily at 7 pm in some famous institute and will commute to it in the same tram for m days. In this tram tickets have eight digits. And Gerald wants to make a surprise for Pollard: each day Pollard will receive a tram k-lucky ticket. The conductor has already agreed to give Pollard certain tickets during all these m days and he only wants Gerald to tell him what kind of tickets to give out. In this regard, help Gerald pick exactly m distinct k-lucky tickets.

Input

The single line contains two integers k and m (0 ≤ k ≤ 104, 1 ≤ m ≤ 3·105).

Output

Print m lines. Each line must contain exactly 8 digits — the k-winning ticket. The tickets may begin with 0, all tickets must be distinct. If there are more than m distinct k-lucky tickets, print any m of them. It is guaranteed that at least m distinct k-lucky tickets exist. The tickets can be printed in any order.

Examples

Input

0 3


Output

00000000
00000001
00000002


Input

7 4


Output

00000007
00000016
00000017
00000018

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
unsigned long number(unsigned long d0, unsigned long d1) {
  return d0 * 10 + d1;
}
unsigned long number(unsigned long d0, unsigned long d1, unsigned long d2) {
  return d0 * 100 + d1 * 10 + d2;
}
unsigned long number(unsigned long d0, unsigned long d1, unsigned long d2,
                     unsigned long d3) {
  return d0 * 1000 + d1 * 100 + d2 * 10 + d3;
  ;
}
string num_string(unsigned long d0, unsigned long d1, unsigned long d2,
                  unsigned long d3) {
  string result;
  result.push_back(d0 + '0');
  result.push_back(d1 + '0');
  result.push_back(d2 + '0');
  result.push_back(d3 + '0');
  return result;
}
int main(void) {
  ios::sync_with_stdio(false);
  unsigned long k = 0, m = 0;
  cin >> k >> m;
  map<long, set<string> > options;
  for (unsigned long x = 0; x <= 9999; x++) {
    unsigned long x_remain = x;
    unsigned long x3 = x_remain % 10;
    x_remain /= 10;
    unsigned long x2 = x_remain % 10;
    x_remain /= 10;
    unsigned long x1 = x_remain % 10;
    x_remain /= 10;
    unsigned long x0 = x_remain % 10;
    string x_str = num_string(x0, x1, x2, x3);
    options[x0 + x1 + x2 + x3].insert(x_str);
    options[x0 + x1 + x2 - x3].insert(x_str);
    options[x0 + x1 - x2 + x3].insert(x_str);
    options[x0 - x1 + x2 + x3].insert(x_str);
    options[x0 + x1 - x2 - x3].insert(x_str);
    options[x0 - x1 - x2 + x3].insert(x_str);
    options[x0 - x1 + x2 - x3].insert(x_str);
    options[x0 + x1 + x2 * x3].insert(x_str);
    options[x0 + x1 * x2 + x3].insert(x_str);
    options[x0 * x1 + x2 + x3].insert(x_str);
    options[x0 * x1 + x2 * x3].insert(x_str);
    options[x0 * x1 * x2 + x3].insert(x_str);
    options[x0 + x1 * x2 * x3].insert(x_str);
    options[x0 - x1 * x2 * x3].insert(x_str);
    options[x0 + x1 + x2 + x3].insert(x_str);
    options[x0 + x1 + (x2 - x3)].insert(x_str);
    options[x0 + (x1 - x2) + x3].insert(x_str);
    options[x0 - (x1 + x2) + x3].insert(x_str);
    options[x0 + (x1 - x2 - x3)].insert(x_str);
    options[x0 - x1 - (x2 + x3)].insert(x_str);
    options[(x0 - x1) + x2 - x3].insert(x_str);
    options[x0 + (x1 + x2) * x3].insert(x_str);
    options[(x0 + x1) * x2 + x3].insert(x_str);
    options[x0 * (x1 + x2) + x3].insert(x_str);
    options[x0 * (x1 + x2 * x3)].insert(x_str);
    options[x0 * (x1 * x2 + x3)].insert(x_str);
    options[(x0 + x1) * x2 * x3].insert(x_str);
    options[(x0 - x1) * x2 * x3].insert(x_str);
    unsigned long x0x1 = number(x0, x1);
    unsigned long x2x3 = number(x2, x3);
    unsigned long x0x1x2 = number(x0, x1, x2);
    unsigned long x1x2x3 = number(x1, x2, x3);
    options[x0 + x1 + x2x3].insert(x_str);
    options[x0 - x1 + x2x3].insert(x_str);
    options[x0 + x1 - x2x3].insert(x_str);
    options[x0 - x1 - x2x3].insert(x_str);
    options[x0 + x1 * x2x3].insert(x_str);
    options[x0 * x1 + x2x3].insert(x_str);
    options[x0 * x1 * x2x3].insert(x_str);
    options[x0x1 + x2x3].insert(x_str);
    options[x0x1 - x2x3].insert(x_str);
    options[x0x1 * x2x3].insert(x_str);
    options[x0x1x2 + x3].insert(x_str);
    options[x0x1x2 - x3].insert(x_str);
    options[x0 + x1x2x3].insert(x_str);
    options[x0 - x1x2x3].insert(x_str);
    options[x0 + x1 * (x2 + x3)].insert(x_str);
    options[(x0 + x1) * (x2 + x3)].insert(x_str);
    options[(x0 + x1 + x2) * x3].insert(x_str);
    options[x0x1 * (x2 + x3)].insert(x_str);
    options[x0x1 * (x2 - x3)].insert(x_str);
    options[x0x1 * (x2 + x3)].insert(x_str);
    options[x0 + x1 * x2x3].insert(x_str);
    options[(x0 - x1) + x2x3].insert(x_str);
    options[(x0 * x1) - x2x3].insert(x_str);
    options[x0 - (x1 - x2x3)].insert(x_str);
    options[(x0 + x1) * x2x3].insert(x_str);
    options[x0 * (x1 + x2x3)].insert(x_str);
    options[(x0 + x1) * (x2 + x3)].insert(x_str);
    options[(x0 + x1 - x2) * x3].insert(x_str);
    options[x0 + (x1 * x2 * x3)].insert(x_str);
    options[x0 + x1 * (x2 - x3)].insert(x_str);
    options[x0 + (x1 - x2) * x3].insert(x_str);
    options[x0 * (x1 + x2) + x3].insert(x_str);
    options[x0 * (x1 - x2 - x3)].insert(x_str);
    options[x0 * (x1 - x2 + x3)].insert(x_str);
    options[x0 * (x1 + x2 - x3)].insert(x_str);
    options[x0 * x1 - (x2 + x3)].insert(x_str);
    options[(x0 - x1) + x2 * x3].insert(x_str);
    options[x0 * (x1 + x2) * x3].insert(x_str);
    options[(x0 + x1) * x2 - x3].insert(x_str);
    options[x0 * (x1 + x2) - x3].insert(x_str);
    options[x0 * (x1 * x2 + x3)].insert(x_str);
    options[(x0 + x1) * (x2 - x3)].insert(x_str);
    options[(x0 - x1) * (x2 - x3)].insert(x_str);
  }
  set<string> output;
  for (map<long, set<string> >::iterator options_it = options.begin();
       options_it != options.end(); ++options_it) {
    long y = 0;
    long x = options_it->first;
    if (x < k) {
      y = k - x;
    } else {
      y = k + x;
    }
    if (y < 0 || y > 9999) continue;
    unsigned long y_remain = y;
    unsigned long y3 = y_remain % 10;
    y_remain /= 10;
    unsigned long y2 = y_remain % 10;
    y_remain /= 10;
    unsigned long y1 = y_remain % 10;
    y_remain /= 10;
    unsigned long y0 = y_remain % 10;
    string y_str = num_string(y0, y1, y2, y3);
    for (set<string>::iterator set_it = options_it->second.begin();
         set_it != options_it->second.end(); ++set_it) {
      output.insert(y_str + *set_it);
    }
    if (output.size() >= m) break;
  }
  unsigned long i = 0;
  for (set<string>::iterator output_it = output.begin();
       output_it != output.end(); ++output_it, i++) {
    if (i == m) break;
    cout << *output_it << endl;
  }
  return 0;
}