#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.141592653589793;
const long double E = 2.71828182845904523;
const long long LLINF = 4000000009000000099;
const long long INF = 2009000099;
const long long MOD7 = 1000000007;
const long long MOD9 = 1000000009;
template <class A, class B, class C>
struct triple {
  A first;
  B second;
  C third;
  triple(A, B, C);
  triple();
};
template <class A, class B, class C>
triple<A, B, C>::triple(A a, B b, C c) {
  first = a;
  second = b;
  third = c;
}
template <class A, class B, class C>
triple<A, B, C>::triple() {}
template <class A, class B, class C>
triple<A, B, C> make_triple(A a, B b, C c) {
  triple<A, B, C> t(a, b, c);
  return t;
}
template <class A, class B, class C>
bool operator<(triple<A, B, C> a, triple<A, B, C> b) {
  if (a.first != b.first) return a.first < b.first;
  if (a.second != b.second) return a.second < b.second;
  if (a.third != b.third) return a.third < b.third;
}
template <class T>
T inline sqr(T a) {
  return a * a;
}
long long bpow(long long a, long long d, long long mod) {
  if (d == 0) return 1;
  long long t = bpow(a, d / 2, mod);
  t = (t * t) % mod;
  if (d & 1) t = (t * a) % mod;
  return t;
}
long long bpow(long long a, long long d) {
  if (d == 1) return a;
  long long t = bpow(a, d / 2);
  t = (t * t);
  if (d & 1) t = (t * a);
  return t;
}
long long gcd(long long a, long long b) {
  while (a && b)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long C(long long n, long long k) {
  long long res = 1;
  for (int i = 1; i <= k; ++i) res = res * (n - k + i) / i;
  return res;
}
long long C(long long n, long long k, long long mod) {
  long long u = 1, d = 1;
  for (int i = 2; i <= n; ++i) u = (u * i) % mod;
  int x = max(k, n - k), z = min(k, n - k);
  for (int i = 2; i <= x; ++i) {
    d = (d * i) % mod;
    if (i <= z) d = (d * i) % mod;
  }
  d = bpow(d, mod - 2, mod);
  long long res = (u * d) % mod;
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  vector<int> l(n);
  for (int i = 0; i < n; ++i) cin >> l[i];
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    int val = 0, lbound = 0;
    if (l[i]) {
      val += ans[l[i] - 1];
      lbound = l[i] + k;
    }
    val += max(min(i + k, n - 1) - max(i - k, lbound) + 1, 0);
    ans[i] = val;
  }
  for (int i = 0; i < n; ++i) cout << ans[i] << " ";
}

### Prompt

Generate 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>
using namespace std;
const long double PI = 3.141592653589793;
const long double E = 2.71828182845904523;
const long long LLINF = 4000000009000000099;
const long long INF = 2009000099;
const long long MOD7 = 1000000007;
const long long MOD9 = 1000000009;
template <class A, class B, class C>
struct triple {
  A first;
  B second;
  C third;
  triple(A, B, C);
  triple();
};
template <class A, class B, class C>
triple<A, B, C>::triple(A a, B b, C c) {
  first = a;
  second = b;
  third = c;
}
template <class A, class B, class C>
triple<A, B, C>::triple() {}
template <class A, class B, class C>
triple<A, B, C> make_triple(A a, B b, C c) {
  triple<A, B, C> t(a, b, c);
  return t;
}
template <class A, class B, class C>
bool operator<(triple<A, B, C> a, triple<A, B, C> b) {
  if (a.first != b.first) return a.first < b.first;
  if (a.second != b.second) return a.second < b.second;
  if (a.third != b.third) return a.third < b.third;
}
template <class T>
T inline sqr(T a) {
  return a * a;
}
long long bpow(long long a, long long d, long long mod) {
  if (d == 0) return 1;
  long long t = bpow(a, d / 2, mod);
  t = (t * t) % mod;
  if (d & 1) t = (t * a) % mod;
  return t;
}
long long bpow(long long a, long long d) {
  if (d == 1) return a;
  long long t = bpow(a, d / 2);
  t = (t * t);
  if (d & 1) t = (t * a);
  return t;
}
long long gcd(long long a, long long b) {
  while (a && b)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long C(long long n, long long k) {
  long long res = 1;
  for (int i = 1; i <= k; ++i) res = res * (n - k + i) / i;
  return res;
}
long long C(long long n, long long k, long long mod) {
  long long u = 1, d = 1;
  for (int i = 2; i <= n; ++i) u = (u * i) % mod;
  int x = max(k, n - k), z = min(k, n - k);
  for (int i = 2; i <= x; ++i) {
    d = (d * i) % mod;
    if (i <= z) d = (d * i) % mod;
  }
  d = bpow(d, mod - 2, mod);
  long long res = (u * d) % mod;
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  vector<int> l(n);
  for (int i = 0; i < n; ++i) cin >> l[i];
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    int val = 0, lbound = 0;
    if (l[i]) {
      val += ans[l[i] - 1];
      lbound = l[i] + k;
    }
    val += max(min(i + k, n - 1) - max(i - k, lbound) + 1, 0);
    ans[i] = val;
  }
  for (int i = 0; i < n; ++i) cout << ans[i] << " ";
}

```