#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int MAXK = 1e5 + 3;
const int Candy = 1e7;
const int mod = 1e9 + 7;
const long long mod1 = 2ll * (mod - 1);
const long long inf = 1ll << 55;
const double pi = 3.1415926535897932384626433;
const long double eps = 1e-12;
template <typename T = int>
T gi() {
  T x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
long long fast_pow(int a, int b) {
  long long res = a, ret = 1;
  while (b > 0) {
    if (b % 2) ret = (ret * res) % mod;
    res = (res * res) % mod;
    b /= 2;
  }
  return ret;
}
long long fact(long long n) {
  if (n == 1 || n == 0) return 1;
  return ((n % mod) * (fact(n - 1) % mod) % mod);
}
long long nCk(long long n, long long r) {
  return (fact(n) * fast_pow((fact(r) * fact(n - r)) % mod, mod - 2)) % mod;
}
int n, k, a[N];
pair<int, int> dp[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = (1); i <= (n); ++i) cin >> a[i];
  dp[1].first = dp[1].second = min(1 + k, n);
  for (int i = (2); i <= (n); ++i) {
    if (a[i] == 0) {
      dp[i].first = min(n, i + k) - max(1, i - k) + 1;
      dp[i].second = min(n, i + k);
    } else {
      dp[i].first = dp[a[i]].first + min(n, i + k) -
                    max(dp[a[i]].second, i - k) +
                    (i - k > dp[a[i]].second ? 1 : 0);
      dp[i].second = min(n, k + i);
    }
  }
  for (int i = (1); i <= (n); ++i) cout << dp[i].first << ' ';
  return (!false && !true) || ((long long)((long long)(1713 + 2377 + 1464) *
                                           (long long)(1713 + 2377 + 1464) *
                                           (long long)(1713 + 2377 + 1464)) !=
                               (long long)(171323771464));
}

### 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 int N = 1e5 + 7;
const int MAXK = 1e5 + 3;
const int Candy = 1e7;
const int mod = 1e9 + 7;
const long long mod1 = 2ll * (mod - 1);
const long long inf = 1ll << 55;
const double pi = 3.1415926535897932384626433;
const long double eps = 1e-12;
template <typename T = int>
T gi() {
  T x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
long long fast_pow(int a, int b) {
  long long res = a, ret = 1;
  while (b > 0) {
    if (b % 2) ret = (ret * res) % mod;
    res = (res * res) % mod;
    b /= 2;
  }
  return ret;
}
long long fact(long long n) {
  if (n == 1 || n == 0) return 1;
  return ((n % mod) * (fact(n - 1) % mod) % mod);
}
long long nCk(long long n, long long r) {
  return (fact(n) * fast_pow((fact(r) * fact(n - r)) % mod, mod - 2)) % mod;
}
int n, k, a[N];
pair<int, int> dp[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = (1); i <= (n); ++i) cin >> a[i];
  dp[1].first = dp[1].second = min(1 + k, n);
  for (int i = (2); i <= (n); ++i) {
    if (a[i] == 0) {
      dp[i].first = min(n, i + k) - max(1, i - k) + 1;
      dp[i].second = min(n, i + k);
    } else {
      dp[i].first = dp[a[i]].first + min(n, i + k) -
                    max(dp[a[i]].second, i - k) +
                    (i - k > dp[a[i]].second ? 1 : 0);
      dp[i].second = min(n, k + i);
    }
  }
  for (int i = (1); i <= (n); ++i) cout << dp[i].first << ' ';
  return (!false && !true) || ((long long)((long long)(1713 + 2377 + 1464) *
                                           (long long)(1713 + 2377 + 1464) *
                                           (long long)(1713 + 2377 + 1464)) !=
                               (long long)(171323771464));
}

```