#include <bits/stdc++.h>
using namespace std;
const int chartointdiff = 48;
vector<long long> to_binary(long long n) {
  int i = 7;
  vector<long long> ans(8);
  while (n >= 2) {
    ans[i] = n % 2;
    n /= 2;
    i--;
  }
  ans[i] = n;
  return ans;
}
long long digitSum(long long n) {
  long long ans = 0;
  while (n > 0) {
    ans += (n % 10);
    n /= 10;
  }
  return ans;
}
long long digitsCount(long long n) {
  long long ans = 0;
  while (n > 0) {
    ans++;
    n /= 10;
  }
  return ans;
}
bool cmp(pair<long long, long long> p1, pair<long long, long long> p2) {
  return (p1.first < p2.first);
}
map<long long, long long> primefactorisation(long long n) {
  map<long long, long long> mp;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      mp[i] = 0;
      while (n % i == 0) {
        mp[i]++;
        n /= i;
      }
    }
  }
  if (n > 1) {
    mp[n] = 1;
  }
  return mp;
}
vector<bool> seive(long long n) {
  vector<bool> arr(n + 1, true);
  for (int i = 2; i * i <= n; i++) {
    if (arr[i]) {
      for (int j = i * i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr;
}
long long power(long long x, long long y) {
  if (y == 0) {
    return (long long)1;
  } else if (y % 2 == 0)
    return power(x, y / 2) * power(x, y / 2);
  else
    return x * power(x, y / 2) * power(x, y / 2);
}
bool isprime(long long x) {
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      return 0;
    }
  }
  return 1;
}
vector<string> bor = {"YES", "NO"};
void solve() {
  long long n, k;
  cin >> n >> k;
  vector<long long> arr(n + 1);
  for (int i = 1; i <= n; i++) cin >> arr[i];
  vector<long long> dp(n + 1);
  vector<long long> lef(n + 1);
  vector<long long> rig(n + 1);
  dp[0] = (long long)0;
  for (long long i = 1; i <= n; i++) {
    rig[i] = i + min(k, n - i);
    lef[i] = i - min(k, i - 1);
    dp[i] = (long long)1 + min(k, n - i) + min(k, i - 1);
    dp[i] += dp[arr[i]];
    if (lef[i] <= rig[arr[i]]) {
      dp[i] -= (rig[arr[i]] - lef[i] + 1);
    }
  }
  for (int i = 1; i <= n; i++) cout << dp[i] << " ";
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
  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 int chartointdiff = 48;
vector<long long> to_binary(long long n) {
  int i = 7;
  vector<long long> ans(8);
  while (n >= 2) {
    ans[i] = n % 2;
    n /= 2;
    i--;
  }
  ans[i] = n;
  return ans;
}
long long digitSum(long long n) {
  long long ans = 0;
  while (n > 0) {
    ans += (n % 10);
    n /= 10;
  }
  return ans;
}
long long digitsCount(long long n) {
  long long ans = 0;
  while (n > 0) {
    ans++;
    n /= 10;
  }
  return ans;
}
bool cmp(pair<long long, long long> p1, pair<long long, long long> p2) {
  return (p1.first < p2.first);
}
map<long long, long long> primefactorisation(long long n) {
  map<long long, long long> mp;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      mp[i] = 0;
      while (n % i == 0) {
        mp[i]++;
        n /= i;
      }
    }
  }
  if (n > 1) {
    mp[n] = 1;
  }
  return mp;
}
vector<bool> seive(long long n) {
  vector<bool> arr(n + 1, true);
  for (int i = 2; i * i <= n; i++) {
    if (arr[i]) {
      for (int j = i * i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr;
}
long long power(long long x, long long y) {
  if (y == 0) {
    return (long long)1;
  } else if (y % 2 == 0)
    return power(x, y / 2) * power(x, y / 2);
  else
    return x * power(x, y / 2) * power(x, y / 2);
}
bool isprime(long long x) {
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      return 0;
    }
  }
  return 1;
}
vector<string> bor = {"YES", "NO"};
void solve() {
  long long n, k;
  cin >> n >> k;
  vector<long long> arr(n + 1);
  for (int i = 1; i <= n; i++) cin >> arr[i];
  vector<long long> dp(n + 1);
  vector<long long> lef(n + 1);
  vector<long long> rig(n + 1);
  dp[0] = (long long)0;
  for (long long i = 1; i <= n; i++) {
    rig[i] = i + min(k, n - i);
    lef[i] = i - min(k, i - 1);
    dp[i] = (long long)1 + min(k, n - i) + min(k, i - 1);
    dp[i] += dp[arr[i]];
    if (lef[i] <= rig[arr[i]]) {
      dp[i] -= (rig[arr[i]] - lef[i] + 1);
    }
  }
  for (int i = 1; i <= n; i++) cout << dp[i] << " ";
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

```