#include <bits/stdc++.h>
using namespace std;
const long long N = 101, OO = 0x3f3f3f3f, mod = 1e9 + 7;
void debug() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct segtree {
  long long size;
  vector<int> minn;
  void init(int n) {
    size = 1;
    while (size < n) size *= 2;
    minn = vector<int>(size * 2);
  }
  int NE = 0;
  int fminn(int &a, int &b) { return a + b; }
  int single(int v) { return v; }
  void set(int i, int v, int x, int xl, int xr) {
    if (xr - xl == 1) {
      minn[x] = single(v);
      return;
    }
    int mid = (xl + xr) / 2;
    if (i < mid) {
      set(i, v, x * 2 + 1, xl, mid);
    } else {
      set(i, v, x * 2 + 2, mid, xr);
    }
    minn[x] = minn[x * 2 + 1] + minn[x * 2 + 2];
  }
  void set(int i, int v) { set(i, v, 0, 0, size); }
  void build(vector<int> &v, int x, int xl, int xr) {
    if (xr - xl == 1) {
      if (xl < (int)v.size()) minn[x] = single(v[xl]);
      return;
    }
    int mid = (xl + xr) / 2;
    build(v, x * 2 + 1, xl, mid);
    build(v, x * 2 + 2, mid, xr);
    minn[x] = minn[x * 2 + 1] + minn[x * 2 + 2];
  }
  void build(vector<int> v) { build(v, 0, 0, size); }
  int calc(int x, int y, int xl, int xr, int xx) {
    if (x <= xl && y >= xr) return minn[xx];
    if (x >= xr || y <= xl) return NE;
    int mid = (xl + xr) / 2;
    int first = calc(x, y, xl, mid, xx * 2 + 1);
    int second = calc(x, y, mid, xr, xx * 2 + 2);
    return fminn(first, second);
  }
  int calc(int x, int y) { return calc(x, y, 0, size, 0); }
  int find(int k, int x, int xl, int xr) {
    if (xr - xl == 1) {
      return xl;
    }
    int op = minn[2 * x + 1];
    int mid = (xl + xr) / 2;
    if (k < op) {
      return find(k, x * 2 + 1, xl, mid);
    } else
      return find(k - op, x * 2 + 2, mid, xr);
  }
  int find(int k) { return find(k, 0, 0, size); }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> v(n + 1);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
  }
  int dp[n + 1];
  for (int i = 0; i < n; ++i) {
    dp[i] = min(n - 1, k + i) - max(i - k, 0) + 1;
    if (v[i]) {
      dp[i] +=
          dp[v[i] - 1] - max(0, min(n - 1, k + v[i] - 1) - max(i - k, 0) + 1);
    }
    cout << dp[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;
const long long N = 101, OO = 0x3f3f3f3f, mod = 1e9 + 7;
void debug() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug(T...);
}
struct segtree {
  long long size;
  vector<int> minn;
  void init(int n) {
    size = 1;
    while (size < n) size *= 2;
    minn = vector<int>(size * 2);
  }
  int NE = 0;
  int fminn(int &a, int &b) { return a + b; }
  int single(int v) { return v; }
  void set(int i, int v, int x, int xl, int xr) {
    if (xr - xl == 1) {
      minn[x] = single(v);
      return;
    }
    int mid = (xl + xr) / 2;
    if (i < mid) {
      set(i, v, x * 2 + 1, xl, mid);
    } else {
      set(i, v, x * 2 + 2, mid, xr);
    }
    minn[x] = minn[x * 2 + 1] + minn[x * 2 + 2];
  }
  void set(int i, int v) { set(i, v, 0, 0, size); }
  void build(vector<int> &v, int x, int xl, int xr) {
    if (xr - xl == 1) {
      if (xl < (int)v.size()) minn[x] = single(v[xl]);
      return;
    }
    int mid = (xl + xr) / 2;
    build(v, x * 2 + 1, xl, mid);
    build(v, x * 2 + 2, mid, xr);
    minn[x] = minn[x * 2 + 1] + minn[x * 2 + 2];
  }
  void build(vector<int> v) { build(v, 0, 0, size); }
  int calc(int x, int y, int xl, int xr, int xx) {
    if (x <= xl && y >= xr) return minn[xx];
    if (x >= xr || y <= xl) return NE;
    int mid = (xl + xr) / 2;
    int first = calc(x, y, xl, mid, xx * 2 + 1);
    int second = calc(x, y, mid, xr, xx * 2 + 2);
    return fminn(first, second);
  }
  int calc(int x, int y) { return calc(x, y, 0, size, 0); }
  int find(int k, int x, int xl, int xr) {
    if (xr - xl == 1) {
      return xl;
    }
    int op = minn[2 * x + 1];
    int mid = (xl + xr) / 2;
    if (k < op) {
      return find(k, x * 2 + 1, xl, mid);
    } else
      return find(k - op, x * 2 + 2, mid, xr);
  }
  int find(int k) { return find(k, 0, 0, size); }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> v(n + 1);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
  }
  int dp[n + 1];
  for (int i = 0; i < n; ++i) {
    dp[i] = min(n - 1, k + i) - max(i - k, 0) + 1;
    if (v[i]) {
      dp[i] +=
          dp[v[i] - 1] - max(0, min(n - 1, k + v[i] - 1) - max(i - k, 0) + 1);
    }
    cout << dp[i] << " ";
  }
  return 0;
}

```