Problem: Polycarpus has a computer with n processors. Also, his computer has n memory cells. We'll consider the processors numbered by integers from 1 to n and that the memory cells are consecutively numbered by integers from 1 to n.

Polycarpus needs to come up with a parallel program model. For each memory cell number i this program must record the value n - i to this cell. In other words, for each cell you've got to find the distance to cell n.

Let's denote the value that is written in the i-th cell as ai. Initially, ai = 1 (1 ≤ i < n) and an = 0. We will consider that only processor i can write values in the memory cell number i. All processors can read an information from some cell (several processors can read an information from some cell simultaneously).

The parallel program is executed in several steps. During each step we execute the parallel version of the increment operation. Executing the parallel version of the increment operation goes as follows:

  1. Each processor independently of the other ones chooses some memory cell. Let's say that processor i has chosen a cell with number ci (1 ≤ ci ≤ n). 
  2. All processors simultaneously execute operation ai = ai + aci. 



Help Polycarpus come up with the parallel program model that is executed in exactly k steps. Calculate the operations that need to be executed. Note that after k steps for all i's value ai must be equal n - i.

Input

The first line contains two space-separated integers n and k (1 ≤ n ≤ 104, 1 ≤ k ≤ 20).

It is guaranteed that at the given n and k the required sequence of operations exists.

Output

Print exactly n·k integers in k lines. In the first line print numbers c1, c2, ..., cn (1 ≤ ci ≤ n) for the first increment operation. In the second line print the numbers for the second increment operation. In the k-th line print the numbers for the k-th increment operation.

As a result of the printed operations for any i value ai must equal n - i.

Examples

Input

1 1


Output

1


Input

3 2


Output

2 3 3
3 3 3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const double EPS = 1e-7;
double iabs(const double a) { return (a < -EPS) ? -a : a; }
double imin(const double a, const double b) { return (a - b > EPS) ? b : a; }
double imax(const double a, const double b) { return (a - b > EPS) ? a : b; }
template <class I>
I iabs(const I a) {
  return (a < 0) ? -a : a;
}
template <class I>
I imin(const I a, const I b) {
  return (a < b) ? a : b;
}
template <class I>
I imax(const I a, const I b) {
  return (a < b) ? b : a;
}
template <class I>
inline I mod_pow(const I& x, const long long p, const I& m) {
  if (p == 0) return 1;
  I mult = (p & 1) ? x : 1;
  I t = mod_pow(x, p / 2, m) % m;
  return (((mult * t) % m) * t) % m;
}
template <class T>
inline T ipow(const T& x, const long long p) {
  if (p == 0) return 1;
  T mult = (p & 1) ? x : 1;
  T h = ipow(x, p / 2);
  return h * h * mult;
}
unsigned long long gcd(unsigned long long a, unsigned long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
template <class T>
T next_power_of_two(T v) {
  if (v < 0) return 0;
  v--;
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v |= v >> 32;
  v++;
  return v;
}
string bin(unsigned int i) {
  string res = "";
  while (i != 0) {
    res += ('0' + (i % 2));
    i = i / 2;
  }
  return string(res.rbegin(), res.rend());
}
template <int SIZE>
class DSU {
 public:
  int parent[SIZE];
  int rank[SIZE];
  int count;
  void clear() {
    for (int i = 0; i < SIZE; i++) {
      this->parent[i] = -1;
      this->rank[i] = 0;
    }
    this->count = 0;
  }
  DSU() { this->clear(); }
  void make(int x) {
    this->parent[x] = x;
    this->rank[x] = 1;
    this->count++;
  }
  bool in_a_set(int x) { return this->parent[x] != -1; }
  int find(int x) {
    if (x == this->parent[x]) return x;
    return this->parent[x] = find(this->parent[x]);
  }
  void combine(int x, int y) {
    x = this->find(x);
    y = this->find(y);
    if (x != y) {
      if (this->rank[x] > this->rank[y])
        this->parent[x] = y;
      else
        this->parent[y] = x;
      this->count--;
    }
  }
};
class BigInt {
 public:
  const static unsigned int N = 1000;
  const static unsigned int base = 10;
  unsigned int len;
  short sign;
  unsigned int digits[N];
  BigInt(const BigInt& bi) {
    this->len = bi.len;
    this->sign = bi.sign;
    for (unsigned int i = 0; i < this->len; ++i) (*this)[i] = bi[i];
  }
  BigInt(long long n) {
    this->len = 0;
    this->sign = (n >= 0) ? 1 : -1;
    this->digits[0] = 0;
    while (n) {
      this->digits[this->len] = n % this->base;
      n /= this->base;
      this->len++;
    }
    if (this->len == 0) this->len = 1;
  }
  BigInt(string s) {
    this->sign = (s[0] == '-') ? 1 : -1;
    this->digits[0] = 0;
    if (s[0] == '-') s = s.substr(1, s.length() - 1);
    this->len = s.length();
    for (unsigned int i = 0; i < this->len; i++)
      (*this)[i] = s[this->len - i - 1] - '0';
  }
  string toString() const {
    stringstream ss;
    for (int i = this->len - 1; i >= 0; --i) ss << (*this)[i];
    return ss.str();
  }
  unsigned int& operator[](const unsigned int i) { return digits[i]; }
  unsigned int operator[](const unsigned int i) const {
    if (i < this->len) return this->digits[i];
    return 0;
  }
  bool iszero() const {
    if (this->len <= 1 && this->digits[0] == 0) return true;
    return false;
  }
  BigInt& operator=(const BigInt& rval) {
    if (this != &rval) {
      this->len = rval.len;
      this->sign = rval.sign;
      for (unsigned int i = 0; i < this->len; ++i) (*this)[i] = rval[i];
    }
    return *this;
  }
  BigInt operator+(const BigInt& rhs) const {
    BigInt s(0);
    unsigned long long r = 0, d, i;
    for (i = 0; i < max(this->len, rhs.len); i++) {
      d = (*this)[i] + rhs[i] + r;
      r = d / this->base;
      s[i] = d % this->base;
    }
    s.len = max(this->len, rhs.len);
    if (r) s[s.len++] = r;
    return s;
  }
  BigInt operator+(unsigned long long rhs) const {
    BigInt s(*this);
    unsigned long long r = 0, d, i = 0;
    while (rhs != 0 || r != 0) {
      d = s[i] + (rhs % s.base) + r;
      rhs /= s.base;
      r = d / s.base;
      s[i] = d % s.base;
      i++;
    }
    if (i > s.len) s.len = i;
    return s;
  }
  BigInt operator*(unsigned long long rhs) const {
    if (rhs == 0) return BigInt(0);
    BigInt s(*this);
    unsigned long long r = 0, d, i;
    for (i = 0; i < s.len; ++i) {
      d = s[i] * rhs + r;
      r = d / this->base;
      s[i] = d % this->base;
    }
    while (r) s[s.len++] = r % this->base, r /= this->base;
    return s;
  }
  BigInt operator*(const BigInt& rhs) const {
    BigInt s(0);
    if (rhs.iszero()) return s;
    unsigned long long r, d, i, j, k;
    for (i = 0; i < this->N; i++) s[i] = 0;
    for (i = 0; i < this->len; i++) {
      r = 0;
      for (j = 0, k = i; j < rhs.len; j++, k++) {
        d = (*this)[i] * rhs[j] + r + s[k];
        r = d / this->base;
        s[k] = d % this->base;
      }
      while (r) s[k++] = r % this->base, r /= this->base;
      if (k > s.len) s.len = k;
    }
    while (s.len > 1 && s[s.len - 1] == 0) s.len--;
    return s;
  }
  unsigned int operator%(unsigned int rhs) {
    BigInt t(*this);
    unsigned long long pow = 1;
    unsigned long long mod = 0;
    for (unsigned int i = 0; i < this->len && pow != 0; i++) {
      mod = (((*this)[i] % rhs) * pow + mod) % rhs;
      pow = (pow * this->base) % rhs;
    }
    return mod;
  }
};
vector<long long> genprimes(const int n) {
  vector<long long> res;
  res.push_back(2);
  long long m, t, j;
  for (int i = 3; i <= n; i++) {
    j = 0;
    m = res.size();
    t = (long long)sqrt(i * 1.0) + 1;
    while (j < m && res[j] < t && i % res[j] != 0) j++;
    if (j == m || res[j] >= t) res.push_back(i);
  }
  return res;
}
long long reverse_intereger(long long a) {
  int res = 0;
  while (a != 0) res = 10 * res + (a % 10), a /= 10;
  return res;
}
const long long INF = 1000 * 1000 * 1000 + 100;
const long long N = 100 * 1000 + 10;
const long long M = 1000 * 1000 * 1000 + 7;
int main(int argc, char* argv[]) {
  long long n, k, a[N], i, j, c[N];
  cin >> n >> k;
  for (i = 0; i < n; ++i) a[i] = 1;
  a[n] = 0;
  for (j = 1; j <= k; ++j) {
    long long v = 2 * (j - 1);
    long long m = a[1];
    for (i = 1; i < n; ++i) {
      long long d = n - i - a[i];
      if (d > m)
        cout << "1 ", a[i] += m;
      else
        cout << (n - d) << " ", a[i] += d;
    }
    cout << n << endl;
  }
  return 0;
}