#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "} ";
  return out;
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &arr) {
  for (auto &i : arr) in >> i;
  return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &arr) {
  for (auto i : arr) out << i << " ";
  out << endl;
  return out;
}
vector<int> pp;
vector<pair<int, int>> last;
vector<int> ans;
int main() {
  ios::sync_with_stdio(false);
  cin.tie();
  int n, k;
  cin >> n >> k;
  pp.resize(n);
  last.resize(n);
  ans.resize(n);
  for (int i = 0; i < n; ++i) {
    int p;
    cin >> p;
    if (p != 0) {
      p--;
      pp[i] = p;
    } else {
      pp[i] = -1;
    }
    last[i] = {max(0, i - k), min(n - 1, i + k)};
    ans[i] = last[i].second - last[i].first + 1;
  }
  for (int i = 0; i < n; ++i) {
    int p = pp[i];
    if (pp[i] != -1) {
      auto otr = last[p];
      auto newotr = last[i];
      if (otr.second >= newotr.first) {
        ans[i] = ans[i] - (newotr.second - newotr.first + 1);
        newotr.first = otr.first;
        ans[i] += newotr.second - newotr.first + 1 + ans[p] -
                  (otr.second - otr.first + 1);
        last[i] = newotr;
      } else {
        ans[i] += ans[p];
      }
    }
    cout << ans[i] << ' ';
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "} ";
  return out;
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &arr) {
  for (auto &i : arr) in >> i;
  return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &arr) {
  for (auto i : arr) out << i << " ";
  out << endl;
  return out;
}
vector<int> pp;
vector<pair<int, int>> last;
vector<int> ans;
int main() {
  ios::sync_with_stdio(false);
  cin.tie();
  int n, k;
  cin >> n >> k;
  pp.resize(n);
  last.resize(n);
  ans.resize(n);
  for (int i = 0; i < n; ++i) {
    int p;
    cin >> p;
    if (p != 0) {
      p--;
      pp[i] = p;
    } else {
      pp[i] = -1;
    }
    last[i] = {max(0, i - k), min(n - 1, i + k)};
    ans[i] = last[i].second - last[i].first + 1;
  }
  for (int i = 0; i < n; ++i) {
    int p = pp[i];
    if (pp[i] != -1) {
      auto otr = last[p];
      auto newotr = last[i];
      if (otr.second >= newotr.first) {
        ans[i] = ans[i] - (newotr.second - newotr.first + 1);
        newotr.first = otr.first;
        ans[i] += newotr.second - newotr.first + 1 + ans[p] -
                  (otr.second - otr.first + 1);
        last[i] = newotr;
      } else {
        ans[i] += ans[p];
      }
    }
    cout << ans[i] << ' ';
  }
  return 0;
}

```