#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ul = unsigned long long;
using db = double;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using pd = pair<ld, ld>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long long>;
using vd = vector<ld>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <typename T, size_t size>
using va = vector<array<T, size>>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(ld& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < int(((int)(a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < int(SZ); i++) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr(x.first, " ", x.second);
}
template <class T>
void prContain(const T& x) {
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? " " : "", a), fst = 0;
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace output
using namespace output;
namespace error {
template <class T1, class T2>
void dg(const pair<T1, T2>& x);
template <class T, size_t SZ>
void dg(const array<T, SZ>& x);
template <class T>
void dg(const vector<T>& x);
template <class T>
void dg(const set<T>& x);
template <class T1, class T2>
void dg(const map<T1, T2>& x);
template <class T>
void dg(const T& x) {
  cerr << x;
}
template <class Arg, class... Args>
void dg(const Arg& first, const Args&... rest) {
  dg(first);
  dg(rest...);
}
template <class T1, class T2>
void dg(const pair<T1, T2>& x) {
  dg(x.first, " ", x.second);
}
template <class T>
void dgContain(const T& x) {
  bool fst = 1;
  for (const auto& a : x) dg(!fst ? " " : "", a), fst = 0;
}
template <class T, size_t SZ>
void dg(const array<T, SZ>& x) {
  dgContain(x);
}
template <class T>
void dg(const vector<T>& x) {
  dgContain(x);
}
template <class T>
void dg(const set<T>& x) {
  dgContain(x);
}
template <class T1, class T2>
void dg(const map<T1, T2>& x) {
  dgContain(x);
}
void ds() { dg("\n"); }
template <class Arg>
void ds(const Arg& first) {
  dg(first);
  ds();
}
template <class Arg, class... Args>
void ds(const Arg& first, const Args&... rest) {
  dg(first, " ");
  ds(rest...);
}
}  // namespace error
using namespace error;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  dg(H);
  debug(T...);
}
inline long long modPow(long long x, long long y, long long mod) {
  long long res = 1;
  x = x % mod;
  ;
  while (y > 0) {
    if (y & 1) {
      res = (res * x) % mod;
    }
    y = y >> 1;
    x = (x * x) % mod;
  }
  return res;
}
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
char dirs[4] = {'L', 'D', 'R', 'U'};
unordered_map<char, int> rdirs = {{'R', 2}, {'D', 1}, {'L', 0}, {'U', 3}};
const long long mod = 1e9 + 7;
const long long INF = 2e18 + 6;
const int MXN = 1e6 + 5;
void solve() {
  int n, k;
  re(n, k);
  int ans = 0;
  int cur = 1;
  while (cur < n) {
    cur *= k;
    ans++;
  }
  auto baseTo = [&](int a, int b) {
    vector<int> ans;
    for (int i = 0; i < int(12); i++) {
      ans.push_back(b % a);
      b /= a;
    }
    return ans;
  };
  vector<int> res;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      vi a = baseTo(k, i);
      vi b = baseTo(k, j);
      int p = 11;
      while (p--) {
        if (a[p] != b[p]) {
          res.push_back(p + 1);
          break;
        }
      }
    }
  }
  ps(ans);
  ps(res);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(6);
  int t = 1, tc = 1;
  while (t--) {
    solve();
    tc++;
  }
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

Even if you just leave them be, they will fall to pieces all by themselves. So, someone has to protect them, right?

You find yourself playing with Teucer again in the city of Liyue. As you take the eccentric little kid around, you notice something interesting about the structure of the city.

Liyue can be represented as a directed graph containing n nodes. Nodes are labeled from 1 to n. There is a directed edge from node a to node b if and only if a < b.

A path between nodes a and b is defined as a sequence of edges such that you can start at a, travel along all of these edges in the corresponding direction, and end at b. The length of a path is defined by the number of edges. A rainbow path of length x is defined as a path in the graph such that there exists at least 2 distinct colors among the set of x edges.

Teucer's favorite number is k. You are curious about the following scenario: If you were to label each edge with a color, what is the minimum number of colors needed to ensure that all paths of length k or longer are rainbow paths?

Teucer wants to surprise his older brother with a map of Liyue. He also wants to know a valid coloring of edges that uses the minimum number of colors. Please help him with this task!

Input

The only line of input contains two integers n and k (2 ≤ k < n ≤ 1000). 

Output

On the first line, output c, the minimum colors you need to satisfy the above requirements.

On the second line, print a valid edge coloring as an array of (n(n-1))/(2) integers ranging from 1 to c. Exactly c distinct colors should exist in the construction. Print the edges in increasing order by the start node first, then by the second node.

For example, if n=4, the edge colors will correspond to this order of edges: (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

Examples

Input


5 3


Output


2
1 2 2 2 2 2 2 1 1 1


Input


5 2


Output


3
3 2 2 1 2 2 1 3 1 1 


Input


8 7


Output


2
2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1


Input


3 2


Output


2
1 2 2 

Note

The corresponding construction for the first test case looks like this: 

<image> It is impossible to satisfy the constraints with less than 2 colors.

The corresponding construction for the second test case looks like this: 

<image> One can show there exists no construction using less than 3 colors.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ul = unsigned long long;
using db = double;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using pd = pair<ld, ld>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long long>;
using vd = vector<ld>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <typename T, size_t size>
using va = vector<array<T, size>>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(ld& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < int(((int)(a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < int(SZ); i++) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr(x.first, " ", x.second);
}
template <class T>
void prContain(const T& x) {
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? " " : "", a), fst = 0;
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace output
using namespace output;
namespace error {
template <class T1, class T2>
void dg(const pair<T1, T2>& x);
template <class T, size_t SZ>
void dg(const array<T, SZ>& x);
template <class T>
void dg(const vector<T>& x);
template <class T>
void dg(const set<T>& x);
template <class T1, class T2>
void dg(const map<T1, T2>& x);
template <class T>
void dg(const T& x) {
  cerr << x;
}
template <class Arg, class... Args>
void dg(const Arg& first, const Args&... rest) {
  dg(first);
  dg(rest...);
}
template <class T1, class T2>
void dg(const pair<T1, T2>& x) {
  dg(x.first, " ", x.second);
}
template <class T>
void dgContain(const T& x) {
  bool fst = 1;
  for (const auto& a : x) dg(!fst ? " " : "", a), fst = 0;
}
template <class T, size_t SZ>
void dg(const array<T, SZ>& x) {
  dgContain(x);
}
template <class T>
void dg(const vector<T>& x) {
  dgContain(x);
}
template <class T>
void dg(const set<T>& x) {
  dgContain(x);
}
template <class T1, class T2>
void dg(const map<T1, T2>& x) {
  dgContain(x);
}
void ds() { dg("\n"); }
template <class Arg>
void ds(const Arg& first) {
  dg(first);
  ds();
}
template <class Arg, class... Args>
void ds(const Arg& first, const Args&... rest) {
  dg(first, " ");
  ds(rest...);
}
}  // namespace error
using namespace error;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  dg(H);
  debug(T...);
}
inline long long modPow(long long x, long long y, long long mod) {
  long long res = 1;
  x = x % mod;
  ;
  while (y > 0) {
    if (y & 1) {
      res = (res * x) % mod;
    }
    y = y >> 1;
    x = (x * x) % mod;
  }
  return res;
}
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
char dirs[4] = {'L', 'D', 'R', 'U'};
unordered_map<char, int> rdirs = {{'R', 2}, {'D', 1}, {'L', 0}, {'U', 3}};
const long long mod = 1e9 + 7;
const long long INF = 2e18 + 6;
const int MXN = 1e6 + 5;
void solve() {
  int n, k;
  re(n, k);
  int ans = 0;
  int cur = 1;
  while (cur < n) {
    cur *= k;
    ans++;
  }
  auto baseTo = [&](int a, int b) {
    vector<int> ans;
    for (int i = 0; i < int(12); i++) {
      ans.push_back(b % a);
      b /= a;
    }
    return ans;
  };
  vector<int> res;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      vi a = baseTo(k, i);
      vi b = baseTo(k, j);
      int p = 11;
      while (p--) {
        if (a[p] != b[p]) {
          res.push_back(p + 1);
          break;
        }
      }
    }
  }
  ps(ans);
  ps(res);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(6);
  int t = 1, tc = 1;
  while (t--) {
    solve();
    tc++;
  }
  return 0;
}

```