#include <bits/stdc++.h>
using namespace std;
vector<int> g[100500];
bool used[100500];
class SegTree {
 public:
  SegTree() {}
  void init(int _size_) {
    n = _size_;
    mini = new int[4 * n + 44];
    cnt = new int[4 * n + 44];
    add = new int[4 * n + 44];
    build(0, 0, n - 1);
  }
  void build(int v, int tl, int tr) {
    if (tl == tr) {
      mini[v] = 0;
      cnt[v] = 1;
      add[v] = 0;
      return;
    }
    int tm = (tl + tr) / 2;
    build(v + v + 1, tl, tm);
    build(v + v + 2, tm + 1, tr);
    if (mini[v + v + 1] < mini[v + v + 2]) {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1];
    } else if (mini[v + v + 1] > mini[v + v + 2]) {
      mini[v] = mini[v + v + 2];
      cnt[v] = cnt[v + v + 2];
    } else {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1] + cnt[v + v + 2];
    }
    add[v] = 0;
  }
  void _add_(int v, int tl, int tr, int l, int r, int x) {
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
      add[v] += x;
      mini[v] += x;
      return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    _add_(v + v + 1, tl, tm, l, r, x);
    _add_(v + v + 2, tm + 1, tr, l, r, x);
    if (mini[v + v + 1] < mini[v + v + 2]) {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1];
    } else if (mini[v + v + 1] > mini[v + v + 2]) {
      mini[v] = mini[v + v + 2];
      cnt[v] = cnt[v + v + 2];
    } else {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1] + cnt[v + v + 2];
    }
  }
  void push(int v, int tl, int tr) {
    if (tl == tr) return;
    if (add[v] == 0) return;
    add[v + v + 1] += add[v];
    add[v + v + 2] += add[v];
    mini[v + v + 1] += add[v];
    mini[v + v + 2] += add[v];
    add[v] = 0;
  }
  int GetRes() {
    if (mini[0] != 0)
      return n;
    else
      return n - cnt[0];
  }
  int size() { return n; }

 private:
  int n;
  int *mini;
  int *cnt;
  int *add;
};
int ans[100500];
SegTree T;
void dfs(int v, int n, int k) {
  used[v] = 1;
  T._add_(0, 0, T.size() - 1, max(0, v - k), min(n - 1, v + k), 1);
  ans[v] = T.GetRes();
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i];
    if (!used[to]) dfs(to, n, k);
  }
  T._add_(0, 0, T.size() - 1, max(0, v - k), min(n - 1, k + v), -1);
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  T.init(n);
  int p;
  for (int i = 0; i < n; i++) {
    cin >> p;
    if (!p) continue;
    p--;
    g[p].push_back(i);
    g[i].push_back(p);
  }
  for (int i = 0; i < n; i++) used[i] = 0;
  for (int i = 0; i < n; i++)
    if (!used[i]) dfs(i, n, k);
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued over 10 years ago.

More formal, your message history is a sequence of messages ordered by time sent numbered from 1 to n where n is the total number of messages in the chat.

Each message might contain a link to an earlier message which it is a reply to. When opening a message x or getting a link to it, the dialogue is shown in such a way that k previous messages, message x and k next messages are visible (with respect to message x). In case there are less than k messages somewhere, they are yet all shown.

Digging deep into your message history, you always read all visible messages and then go by the link in the current message x (if there is one) and continue reading in the same manner.

Determine the number of messages you'll read if your start from message number t for all t from 1 to n. Calculate these numbers independently. If you start with message x, the initial configuration is x itself, k previous and k next messages. Messages read multiple times are considered as one.

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ n) — the total amount of messages and the number of previous and next messages visible.

The second line features a sequence of integers a1, a2, ..., an (0 ≤ ai < i), where ai denotes the i-th message link destination or zero, if there's no link from i. All messages are listed in chronological order. It's guaranteed that the link from message x goes to message with number strictly less than x.

Output

Print n integers with i-th denoting the number of distinct messages you can read starting from message i and traversing the links while possible.

Examples

Input

6 0
0 1 1 2 3 2


Output

1 2 2 3 3 3 


Input

10 1
0 1 0 3 4 5 2 3 7 0


Output

2 3 3 4 5 6 6 6 8 2 


Input

2 2
0 1


Output

2 2 

Note

Consider i = 6 in sample case one. You will read message 6, then 2, then 1 and then there will be no link to go.

In the second sample case i = 6 gives you messages 5, 6, 7 since k = 1, then 4, 5, 6, then 2, 3, 4 and then the link sequence breaks. The number of distinct messages here is equal to 6.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> g[100500];
bool used[100500];
class SegTree {
 public:
  SegTree() {}
  void init(int _size_) {
    n = _size_;
    mini = new int[4 * n + 44];
    cnt = new int[4 * n + 44];
    add = new int[4 * n + 44];
    build(0, 0, n - 1);
  }
  void build(int v, int tl, int tr) {
    if (tl == tr) {
      mini[v] = 0;
      cnt[v] = 1;
      add[v] = 0;
      return;
    }
    int tm = (tl + tr) / 2;
    build(v + v + 1, tl, tm);
    build(v + v + 2, tm + 1, tr);
    if (mini[v + v + 1] < mini[v + v + 2]) {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1];
    } else if (mini[v + v + 1] > mini[v + v + 2]) {
      mini[v] = mini[v + v + 2];
      cnt[v] = cnt[v + v + 2];
    } else {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1] + cnt[v + v + 2];
    }
    add[v] = 0;
  }
  void _add_(int v, int tl, int tr, int l, int r, int x) {
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
      add[v] += x;
      mini[v] += x;
      return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    _add_(v + v + 1, tl, tm, l, r, x);
    _add_(v + v + 2, tm + 1, tr, l, r, x);
    if (mini[v + v + 1] < mini[v + v + 2]) {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1];
    } else if (mini[v + v + 1] > mini[v + v + 2]) {
      mini[v] = mini[v + v + 2];
      cnt[v] = cnt[v + v + 2];
    } else {
      mini[v] = mini[v + v + 1];
      cnt[v] = cnt[v + v + 1] + cnt[v + v + 2];
    }
  }
  void push(int v, int tl, int tr) {
    if (tl == tr) return;
    if (add[v] == 0) return;
    add[v + v + 1] += add[v];
    add[v + v + 2] += add[v];
    mini[v + v + 1] += add[v];
    mini[v + v + 2] += add[v];
    add[v] = 0;
  }
  int GetRes() {
    if (mini[0] != 0)
      return n;
    else
      return n - cnt[0];
  }
  int size() { return n; }

 private:
  int n;
  int *mini;
  int *cnt;
  int *add;
};
int ans[100500];
SegTree T;
void dfs(int v, int n, int k) {
  used[v] = 1;
  T._add_(0, 0, T.size() - 1, max(0, v - k), min(n - 1, v + k), 1);
  ans[v] = T.GetRes();
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i];
    if (!used[to]) dfs(to, n, k);
  }
  T._add_(0, 0, T.size() - 1, max(0, v - k), min(n - 1, k + v), -1);
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  T.init(n);
  int p;
  for (int i = 0; i < n; i++) {
    cin >> p;
    if (!p) continue;
    p--;
    g[p].push_back(i);
    g[i].push_back(p);
  }
  for (int i = 0; i < n; i++) used[i] = 0;
  for (int i = 0; i < n; i++)
    if (!used[i]) dfs(i, n, k);
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
  return 0;
}

```