English · Original
Chinese · Translation
Formal · Original
You received a notebook which is called _Death Note_. This notebook has infinite number of pages. A rule is written on the last page (huh) of this notebook. It says: "You have to write names in this notebook during $n$ consecutive days. During the $i$\-th day you have to write exactly $a_i$ names.". You got scared (of course you got scared, who wouldn't get scared if he just receive a notebook which is named _Death Note_ with a some strange rule written in it?).
Of course, you decided to follow this rule. When you calmed down, you came up with a strategy how you will write names in the notebook. You have calculated that each page of the notebook can contain exactly $m$ names. You will start writing names from the first page. You will write names on the current page as long as the limit on the number of names on this page is not exceeded. When the current page is over, you turn the page. Note that you _always_ turn the page when it ends, it doesn't matter if it is the last day or not. If after some day the current page still can hold at least one name, during the next day you will continue writing the names from the current page.
Now you are interested in the following question: how many times will you turn the page during each day? You are interested in the number of pages you will turn each day from $1$ to $n$.
## Input
The first line of the input contains two integers $n$, $m$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^9$) — the number of days you will write names in the notebook and the number of names which can be written on each page of the notebook.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ means the number of names you will write in the notebook during the $i$\-th day.
## Output
Print exactly $n$ integers $t_1, t_2, \dots, t_n$, where $t_i$ is the number of times you will turn the page during the $i$\-th day.
[samples]
## Note
In the first example pages of the _Death Note_ will look like this $[1, 1, 1, 2, 2], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3], [3, 3, 3, 3]$. Each number of the array describes during which day name on the corresponding position will be written. It is easy to see that you should turn the first and the second page during the second day and the third page during the third day.
你收到一本名为 _Death Note_ 的笔记本。这本笔记本有无限多页。在笔记本的最后一页（嗯）上写有一条规则："你必须在这本笔记本上连续写 $n$ 天名字。在第 $i$ 天，你必须恰好写 $a_i$ 个名字。" 你感到害怕了（当然你害怕了，谁收到一本叫 _Death Note_ 且写有奇怪规则的笔记本会不害怕呢？）。
当然，你决定遵守这条规则。当你冷静下来后，你制定了一种在笔记本上写名字的策略。你计算出笔记本的每页恰好可以容纳 $m$ 个名字。你将从第一页开始写名字。你将在当前页上持续写名字，直到该页的名字数量达到上限。当当前页写满时，你会翻页。注意，你 _总是_ 在一页写满时翻页，无论这一天是否是最后一天。如果某天结束后当前页仍至少能再写一个名字，那么在下一天你将继续从当前页开始写名字。
现在你关心的问题是：每天你会翻多少次页？你需要计算从第 $1$ 天到第 $n$ 天，每天翻页的次数。
输入的第一行包含两个整数 $n$, $m$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq m lt.eq 10^9$）——表示你将在笔记本上写名字的天数，以及每页可以写的名字数量。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^9$），其中 $a_i$ 表示你在第 $i$ 天将写的名字数量。
请输出恰好 $n$ 个整数 $t_1, t_2, dots.h, t_n$，其中 $t_i$ 表示你在第 $i$ 天翻页的次数。
在第一个例子中，_Death Note_ 的页面将如下所示：$[ 1, 1, 1, 2, 2 ], [ 2, 2, 2, 2, 2 ], [ 3, 3, 3, 3, 3 ], [ 3, 3, 3, 3 ]$。数组中的每个数字表示对应位置的名字是在哪一天写的。可以清楚地看到，在第二天你需要翻过第一页和第二页，在第三天你需要翻过第三页。
## Input
输入的第一行包含两个整数 $n$, $m$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq m lt.eq 10^9$）——表示你将在笔记本上写名字的天数，以及每页可以写的名字数量。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^9$），其中 $a_i$ 表示你在第 $i$ 天将写的名字数量。
## Output
请输出恰好 $n$ 个整数 $t_1, t_2, dots.h, t_n$，其中 $t_i$ 表示你在第 $i$ 天翻页的次数。
[samples]
## Note
在第一个例子中，_Death Note_ 的页面将如下所示：$[ 1, 1, 1, 2, 2 ], [ 2, 2, 2, 2, 2 ], [ 3, 3, 3, 3, 3 ], [ 3, 3, 3, 3 ]$。数组中的每个数字表示对应位置的名字是在哪一天写的。可以清楚地看到，在第二天你需要翻过第一页和第二页，在第三天你需要翻过第三页。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of days.
Let $ m \in \mathbb{Z}^+ $ be the maximum number of names per page.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i $ is the number of names written on day $ i $.
Let $ s_i \in \mathbb{Z}_{\geq 0} $ denote the number of names already written on the current page at the start of day $ i $, with $ s_1 = 0 $.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 1 \leq m \leq 10^9 $
3. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each day $ i \in \{1, \dots, n\} $, compute $ t_i $, the number of page turns during day $ i $, defined as:
$$
t_i = \left\lfloor \frac{s_i + a_i - 1}{m} \right\rfloor
$$
and update the state for the next day:
$$
s_{i+1} = (s_i + a_i) \bmod m
$$
(with $ s_{n+1} $ unused).
**Output**
The sequence $ (t_1, t_2, \dots, t_n) $.
API Response (JSON)
{
"problem": {
"name": "A. Death Note",
"description": {
"content": "You received a notebook which is called _Death Note_. This notebook has infinite number of pages. A rule is written on the last page (huh) of this notebook. It says: \"You have to write names in this n",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1016A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You received a notebook which is called _Death Note_. This notebook has infinite number of pages. A rule is written on the last page (huh) of this notebook. It says: \"You have to write names in this n...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你收到一本名为 _Death Note_ 的笔记本。这本笔记本有无限多页。在笔记本的最后一页（嗯）上写有一条规则：\"你必须在这本笔记本上连续写 $n$ 天名字。在第 $i$ 天，你必须恰好写 $a_i$ 个名字。\" 你感到害怕了（当然你害怕了，谁收到一本叫 _Death Note_ 且写有奇怪规则的笔记本会不害怕呢？）。\n\n当然，你决定遵守这条规则。当你冷静下来后，你制定了一种在笔记本上写名字的策...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of days. \nLet $ m \\in \\mathbb{Z}^+ $ be the maximum number of names per page. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers...",
"is_translate": false,
"language": "Formal"
}
]
}