#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
using namespace std;
const double eps = 0.000001;
const long double pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const long long MOD = 1e18 + 9;
const long long INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 1e5 + 123;
const int PRI = 555557;
const int pri = 997;
int tests = 1;
int n, m, k;
bool u[N];
vector<int> g[N], st;
int t[N * 4], add[N * 4];
bool tree[N * 4];
int ans[N];
void push(int v, int tl, int tr) {
  if (add[v] == -1) return;
  if (tl != tr) {
    add[(v << 1)] = add[v];
    add[(v << 1) | 1] = add[v];
  }
  t[v] = (tr - tl + 1) * add[v];
  add[v] = -1;
}
void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = n) {
  push(v, tl, tr);
  if (tl > r || tr < l) return;
  if (tl >= l && tr <= r) {
    add[v] = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) >> 1;
  upd(l, r, x, (v << 1), tl, tm);
  upd(l, r, x, (v << 1) | 1, tm + 1, tr);
  t[v] = (t[(v << 1)] + t[(v << 1) | 1]);
}
void dfs(int v, int p = 0) {
  int l = max(v - k, 1);
  int r = min(v + k, n);
  if (p) l = max(l, min(p + k + 1, n + 1));
  ans[v] = ans[p] + max(r - l + 1, 0);
  for (int to : g[v]) dfs(to, v);
}
inline void Solve() {
  cin >> n >> k;
  for (int i = 1; i <= n * 4; i++) add[i] = -1;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if (!x) {
      st.push_back(i);
      continue;
    }
    g[x].push_back(i);
  }
  for (int i = 0; i < st.size(); i++) {
    upd(1, n, 0);
    dfs(st[i]);
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  while (tests--) {
    Solve();
  }
  return 0;
}

### Prompt

Please formulate a cpp solution to 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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
using namespace std;
const double eps = 0.000001;
const long double pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const long long MOD = 1e18 + 9;
const long long INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 1e5 + 123;
const int PRI = 555557;
const int pri = 997;
int tests = 1;
int n, m, k;
bool u[N];
vector<int> g[N], st;
int t[N * 4], add[N * 4];
bool tree[N * 4];
int ans[N];
void push(int v, int tl, int tr) {
  if (add[v] == -1) return;
  if (tl != tr) {
    add[(v << 1)] = add[v];
    add[(v << 1) | 1] = add[v];
  }
  t[v] = (tr - tl + 1) * add[v];
  add[v] = -1;
}
void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = n) {
  push(v, tl, tr);
  if (tl > r || tr < l) return;
  if (tl >= l && tr <= r) {
    add[v] = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) >> 1;
  upd(l, r, x, (v << 1), tl, tm);
  upd(l, r, x, (v << 1) | 1, tm + 1, tr);
  t[v] = (t[(v << 1)] + t[(v << 1) | 1]);
}
void dfs(int v, int p = 0) {
  int l = max(v - k, 1);
  int r = min(v + k, n);
  if (p) l = max(l, min(p + k + 1, n + 1));
  ans[v] = ans[p] + max(r - l + 1, 0);
  for (int to : g[v]) dfs(to, v);
}
inline void Solve() {
  cin >> n >> k;
  for (int i = 1; i <= n * 4; i++) add[i] = -1;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if (!x) {
      st.push_back(i);
      continue;
    }
    g[x].push_back(i);
  }
  for (int i = 0; i < st.size(); i++) {
    upd(1, n, 0);
    dfs(st[i]);
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  while (tests--) {
    Solve();
  }
  return 0;
}

```