#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const int mod = inf + 7;
const double eps = 1e-9;
const double pi = acos(-1.0);
struct tree {
  int mn, cnt, add;
} t[400400];
int dp[100100], n, k, a[100100];
vector<int> g[100100];
void push(int v, int tl, int tr) {
  if (t[v].add != 0) {
    if (tl == tr) {
      t[v].mn += t[v].add;
      t[v].add = 0;
    } else {
      t[v + v].add += t[v].add;
      t[v + v + 1].add += t[v].add;
      t[v].mn += t[v].add;
      t[v].add = 0;
    }
  }
}
tree merge(tree a, tree b) {
  tree c;
  c.add = 0;
  c.mn = min(a.mn + a.add, b.mn + b.add);
  c.cnt = 0;
  if (a.mn + a.add == c.mn) c.cnt += a.cnt;
  if (b.mn + b.add == c.mn) c.cnt += b.cnt;
  return c;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v].mn = 0;
    t[v].cnt = 1;
    return;
  }
  int mid = (tl + tr) >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
  t[v] = merge(t[v + v], t[v + v + 1]);
}
pair<int, int> get(int v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (r < tl || l > tr) return make_pair(inf, 0);
  if (l <= tl && tr <= r) return make_pair(t[v].mn, t[v].cnt);
  int mid = (tl + tr) >> 1;
  pair<int, int> a = get(v + v, tl, mid, l, r);
  pair<int, int> b = get(v + v + 1, mid + 1, tr, l, r);
  if (a.first != b.first) return min(a, b);
  return make_pair(a.first, a.second + b.second);
}
void update(int v, int tl, int tr, int l, int r, int val) {
  push(v, tl, tr);
  if (r < tl || l > tr) return;
  if (l <= tl && tr <= r) {
    t[v].add += val;
    return;
  }
  int mid = (tl + tr) >> 1;
  update(v + v, tl, mid, l, r, val);
  update(v + v + 1, mid + 1, tr, l, r, val);
  t[v] = merge(t[v + v], t[v + v + 1]);
}
int calc() {
  pair<int, int> a = get(1, 1, n, 1, n);
  if (a.first == 0) return n - a.second;
  return n;
}
void dfs(int v) {
  int l = max(v - k, 1), r = min(v + k, n);
  update(1, 1, n, l, r, 1);
  dp[v] = calc();
  for (int i = 0; i < g[v].size(); ++i) {
    int to = g[v][i];
    dfs(to);
  }
  update(1, 1, n, l, r, -1);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    g[a[i]].push_back(i);
  }
  build(1, 1, n);
  for (int i = 0; i < (int)g[0].size(); ++i) {
    dfs(g[0][i]);
  }
  for (int i = 1; i <= n; ++i) {
    cout << dp[i] << " ";
  }
  cout << endl;
}

### Prompt

In cpp, your task is to solve 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 int inf = (int)1e9;
const int mod = inf + 7;
const double eps = 1e-9;
const double pi = acos(-1.0);
struct tree {
  int mn, cnt, add;
} t[400400];
int dp[100100], n, k, a[100100];
vector<int> g[100100];
void push(int v, int tl, int tr) {
  if (t[v].add != 0) {
    if (tl == tr) {
      t[v].mn += t[v].add;
      t[v].add = 0;
    } else {
      t[v + v].add += t[v].add;
      t[v + v + 1].add += t[v].add;
      t[v].mn += t[v].add;
      t[v].add = 0;
    }
  }
}
tree merge(tree a, tree b) {
  tree c;
  c.add = 0;
  c.mn = min(a.mn + a.add, b.mn + b.add);
  c.cnt = 0;
  if (a.mn + a.add == c.mn) c.cnt += a.cnt;
  if (b.mn + b.add == c.mn) c.cnt += b.cnt;
  return c;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v].mn = 0;
    t[v].cnt = 1;
    return;
  }
  int mid = (tl + tr) >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
  t[v] = merge(t[v + v], t[v + v + 1]);
}
pair<int, int> get(int v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (r < tl || l > tr) return make_pair(inf, 0);
  if (l <= tl && tr <= r) return make_pair(t[v].mn, t[v].cnt);
  int mid = (tl + tr) >> 1;
  pair<int, int> a = get(v + v, tl, mid, l, r);
  pair<int, int> b = get(v + v + 1, mid + 1, tr, l, r);
  if (a.first != b.first) return min(a, b);
  return make_pair(a.first, a.second + b.second);
}
void update(int v, int tl, int tr, int l, int r, int val) {
  push(v, tl, tr);
  if (r < tl || l > tr) return;
  if (l <= tl && tr <= r) {
    t[v].add += val;
    return;
  }
  int mid = (tl + tr) >> 1;
  update(v + v, tl, mid, l, r, val);
  update(v + v + 1, mid + 1, tr, l, r, val);
  t[v] = merge(t[v + v], t[v + v + 1]);
}
int calc() {
  pair<int, int> a = get(1, 1, n, 1, n);
  if (a.first == 0) return n - a.second;
  return n;
}
void dfs(int v) {
  int l = max(v - k, 1), r = min(v + k, n);
  update(1, 1, n, l, r, 1);
  dp[v] = calc();
  for (int i = 0; i < g[v].size(); ++i) {
    int to = g[v][i];
    dfs(to);
  }
  update(1, 1, n, l, r, -1);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    g[a[i]].push_back(i);
  }
  build(1, 1, n);
  for (int i = 0; i < (int)g[0].size(); ++i) {
    dfs(g[0][i]);
  }
  for (int i = 1; i <= n; ++i) {
    cout << dp[i] << " ";
  }
  cout << endl;
}

```