You are given a permutation P_1 ... P_N of the set {1, 2, ..., N}.

You can apply the following operation to this permutation, any number of times (possibly zero):

* Choose two indices i,j (1 ≦ i < j ≦ N), such that j - i ≧ K and |P_i - P_j| = 1. Then, swap the values of P_i and P_j.



Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one.

Constraints

* 2≦N≦500,000
* 1≦K≦N-1
* P is a permutation of the set {1, 2, ..., N}.

Input

The input is given from Standard Input in the following format:


N K
P_1 P_2 ... P_N


Output

Print the lexicographically smallest permutation that can be obtained.

Examples

Input

4 2
4 2 3 1


Output

2
1
4
3


Input

5 1
5 4 3 2 1


Output

1
2
3
4
5


Input

8 3
4 5 7 8 3 1 2 6


Output

1
2
6
7
5
3
4
8
#include <bits/stdc++.h>
using namespace std;
namespace {
using Integer = long long;
template <class T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (T& val : vec) is >> val;
  return is;
}
template <class T>
istream& operator,(istream& is, T& val) {
  return is >> val;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  for (int i = 0; i < vec.size(); i++)
    os << vec[i] << (i == vec.size() - 1 ? "" : " ");
  return os;
}
template <class T>
ostream& operator,(ostream& os, const T& val) {
  return os << " " << val;
}
template <class H>
void print(const H& head) {
  cout << head;
}
template <class H, class... T>
void print(const H& head, const T&... tail) {
  cout << head << " ";
  print(tail...);
}
template <class... T>
void println(const T&... values) {
  print(values...);
  cout << endl;
}
template <class H>
void eprint(const H& head) {
  cerr << head;
}
template <class H, class... T>
void eprint(const H& head, const T&... tail) {
  cerr << head << " ";
  eprint(tail...);
}
template <class... T>
void eprintln(const T&... values) {
  eprint(values...);
  cerr << endl;
}
class range {
  long long start_, end_, step_;

 public:
  struct range_iterator {
    long long val, step_;
    range_iterator(long long v, long long step) : val(v), step_(step) {}
    long long operator*() { return val; }
    void operator++() { val += step_; }
    bool operator!=(range_iterator& x) {
      return step_ > 0 ? val < x.val : val > x.val;
    }
  };
  range(long long len) : start_(0), end_(len), step_(1) {}
  range(long long start, long long end) : start_(start), end_(end), step_(1) {}
  range(long long start, long long end, long long step)
      : start_(start), end_(end), step_(step) {}
  range_iterator begin() { return range_iterator(start_, step_); }
  range_iterator end() { return range_iterator(end_, step_); }
};
string operator"" _s(const char* str, size_t size) { return move(string(str)); }
constexpr Integer my_pow(Integer x, Integer k, Integer z = 1) {
  return k == 0    ? z
         : k == 1  ? z * x
         : (k & 1) ? my_pow(x * x, k >> 1, z * x)
                   : my_pow(x * x, k >> 1, z);
}
constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z = 1) {
  return k == 0    ? z % M
         : k == 1  ? z * x % M
         : (k & 1) ? my_pow_mod(x * x % M, k >> 1, M, z * x % M)
                   : my_pow_mod(x * x % M, k >> 1, M, z);
}
constexpr unsigned long long operator"" _ten(unsigned long long value) {
  return my_pow(10, value);
}
inline int k_bit(Integer x, int k) { return (x >> k) & 1; }
mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(
               chrono::steady_clock::now().time_since_epoch())
               .count());
template <class T>
string join(const vector<T>& v, const string& sep) {
  stringstream ss;
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) ss << sep;
    ss << v[i];
  }
  return ss.str();
}
string operator*(string s, int k) {
  string ret;
  while (k) {
    if (k & 1) ret += s;
    s += s;
    k >>= 1;
  }
  return ret;
}
}  // namespace
constexpr long long mod = 9_ten + 7;
using bits = bitset<2002>;
int main() {
  int n, k;
  cin >> n, k;
  vector<vector<int>> G(n);
  vector<vector<int>> dp(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a, b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
    dp[a].push_back(-1);
    dp[b].push_back(-1);
  }
  int ans = 0;
  vector<bits> bb(n);
  for (int i = 0; i < n; i++) {
    function<void(int, int, int)> dfs = [&](int pos, int last, int dist) {
      bb[i].set(pos);
      if (dist == k) return;
      for (int nx : G[pos]) {
        if (nx == last) continue;
        dfs(nx, pos, dist + 1);
      }
    };
    dfs(i, i, 0);
  }
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  shuffle(ord.begin(), ord.end(), mt);
  for (int r_ = 0; r_ < n; r_++) {
    int r = ord[r_];
    vector<int> dist(n);
    function<void(int, int)> dfs = [&](int pos, int last) {
      dist[pos] = dist[last] + 1;
      if (dist[pos] == k) return;
      for (int nx : G[pos]) {
        if (nx == last) continue;
        dfs(nx, pos);
      }
    };
    dist[r] = -1;
    dfs(r, r);
    vector<pair<int, int>> dd;
    for (int i : range(n)) {
      dd.push_back({dist[i], i});
    }
    sort(dd.begin(), dd.end());
    bits s;
    s.set(r);
    for (int i = 0; i < dd.size(); i++) {
      int j = i;
      s.set(dd[i].second);
      while (j + 1 < dd.size() && dd[j + 1].first == dd[i].first) {
        s.set(dd[j + 1].second);
        j++;
      }
      while (1) {
        ans = max<int>(ans, (s & bb[i]).count());
        if (i == j) break;
        i++;
      }
      i = j;
    }
  }
  println(n - ans);
  return 0;
}
