{"raw_statement":[{"iden":"statement","content":"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.\n\nMore 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.\n\nEach 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.\n\nDigging 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.\n\nDetermine 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."},{"iden":"input","content":"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.\n\nThe second line features a sequence of integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < _i_), where _a__i_ 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_."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n6 0\n0 1 1 2 3 2\n\nOutput\n\n1 2 2 3 3 3 \n\nInput\n\n10 1\n0 1 0 3 4 5 2 3 7 0\n\nOutput\n\n2 3 3 4 5 6 6 6 8 2 \n\nInput\n\n2 2\n0 1\n\nOutput\n\n2 2"},{"iden":"note","content":"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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"有时你会想起一位老朋友，以及你们共同经历的一切。幸运的是，有社交网络——它们保存了你所有的消息历史，让你轻松知道十年前你争论过什么。\n\n更正式地，你的消息历史是一个按发送时间排序的消息序列，编号从 #cf_span[1] 到 #cf_span[n]，其中 #cf_span[n] 是聊天中的消息总数。\n\n每条消息可能包含一个指向其回复的较早消息的链接。当打开消息 #cf_span[x] 或获取其链接时，对话会以如下方式显示：#cf_span[k] 条前导消息、消息 #cf_span[x] 以及 #cf_span[k] 条后续消息（相对于消息 #cf_span[x]）。如果某侧的消息少于 #cf_span[k] 条，则全部显示。\n\n在深入查阅你的消息历史时，你总是阅读所有可见消息，然后沿着当前消息 #cf_span[x] 中的链接（如果有）继续阅读，方式相同。\n\n请确定从消息 #cf_span[t] 开始时，你会阅读多少条消息，其中 #cf_span[t] 从 #cf_span[1] 到 #cf_span[n]。这些数字需独立计算。如果你从消息 #cf_span[x] 开始，初始配置为 #cf_span[x] 本身、#cf_span[k] 条前导消息和 #cf_span[k] 条后续消息。重复阅读的消息仅计为一次。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[0 ≤ k ≤ n]）——消息总数和可见的前导与后续消息数量。\n\n第二行包含一个整数序列 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai < i]），其中 #cf_span[ai] 表示第 #cf_span[i] 条消息的链接目标，若无链接则为零。所有消息按时间顺序列出。保证消息 #cf_span[x] 的链接指向编号严格小于 #cf_span[x] 的消息。\n\n请输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示从消息 #cf_span[i] 开始，沿链接不断遍历所能读取的**不同**消息数量。\n\n考虑第一个样例中 #cf_span[i = 6] 的情况：你将阅读消息 #cf_span[6]，然后 #cf_span[2]，然后 #cf_span[1]，之后不再有链接可跳转。\n\n在第二个样例中，当 #cf_span[i = 6] 且 #cf_span[k = 1] 时，你首先看到消息 #cf_span[5, 6, 7]，然后是 #cf_span[4, 5, 6]，接着是 #cf_span[2, 3, 4]，之后链接序列中断。此处不同消息的总数为 #cf_span[6]。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[0 ≤ k ≤ n]）——消息总数和可见的前导与后续消息数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai < i]），其中 #cf_span[ai] 表示第 #cf_span[i] 条消息的链接目标，若无链接则为零。所有消息按时间顺序列出。保证消息 #cf_span[x] 的链接指向编号严格小于 #cf_span[x] 的消息。"},{"iden":"output","content":"请输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示从消息 #cf_span[i] 开始，沿链接不断遍历所能读取的**不同**消息数量。"},{"iden":"examples","content":"输入：\n6 0\n0 1 1 2 3 2\n输出：\n1 2 2 3 3 3\n\n输入：\n10 1\n0 1 0 3 4 5 2 3 7 0\n输出：\n2 3 3 4 5 6 6 6 8 2\n\n输入：\n2 2\n0 1\n输出：\n2 2"},{"iden":"note","content":"考虑第一个样例中 #cf_span[i = 6] 的情况：你将阅读消息 #cf_span[6]，然后 #cf_span[2]，然后 #cf_span[1]，之后不再有链接可跳转。在第二个样例中，当 #cf_span[i = 6] 且 #cf_span[k = 1] 时，你首先看到消息 #cf_span[5, 6, 7]，然后是 #cf_span[4, 5, 6]，接着是 #cf_span[2, 3, 4]，之后链接序列中断。此处不同消息的总数为 #cf_span[6]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $, $ 0 \\leq k \\leq n $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers where $ 0 \\leq a_i < i $ for all $ i \\in \\{1, \\dots, n\\} $, representing the link destination of message $ i $ (0 means no link).  \n\nFor each message $ t \\in \\{1, \\dots, n\\} $, define the **visible set** starting at $ t $ as:  \n$$\nV(t) = \\{ \\max(1, t - k), \\dots, \\min(n, t + k) \\}\n$$  \nDefine the **link graph** $ G = (V, E) $ where $ V = \\{1, \\dots, n\\} $ and $ E = \\{ (i, a_i) \\mid a_i \\neq 0 \\} $, i.e., a directed edge from $ i $ to $ a_i $.  \n\n**Objective**  \nFor each $ t \\in \\{1, \\dots, n\\} $, compute the size of the set of distinct messages read when:  \n1. Starting at message $ t $, add all messages in $ V(t) $ to the read set.  \n2. While the current message $ x $ has a link $ a_x \\neq 0 $, move to $ a_x $, and add all messages in $ V(a_x) $ to the read set.  \n3. Stop when no further links exist.  \n\nLet $ R(t) \\subseteq \\{1, \\dots, n\\} $ be the set of all distinct messages read starting from $ t $.  \nOutput $ |R(t)| $ for each $ t = 1, \\dots, n $.","simple_statement":null,"has_page_source":false}