← 返回题目列表

Codeforces · 518/E

E. 亚瑟和问题

中文机器翻译题面 查看原题

在括号序列之后,亚瑟开始学习数论。他得到了一个新的最喜欢的长度为 n (a1, a2, ..., an) 的序列,由整数和整数 k 组成,不超过 n。

该序列具有以下属性:如果您写出由 k 个连续元素组成的所有段的总和 (a1  +  a2 ...  + ak,  a2  + a3  +  ...  + ak + 1, ...,  an - k + 1  + an - k + 2  +  ...  + an),那么这些数字将形成严格递增序列。

例如,对于以下示例:n = 5, k = 3, a = (1, 2, 4, 5, 6) 数字序列如下所示:(1  + 2  + 4, 2  + 4  + 5, 4  + 5  + 6) = (7, 11, 15),这意味着序列 a 满足所描述的属性。

显然,和序列将有 n - k + 1 个元素。

有人(我们不会说是谁)用问号替换了亚瑟序列中的一些数字(如果这个数字被替换,则它恰好被一个问号替换)。我们需要恢复序列,使其满足所需的属性,并最小化总和 |ai|,其中 |ai|是ai的绝对值。

输入

第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 105),分别表示亚瑟序列中有多少个数字以及段的长度。

下一行包含 n 个空格分隔的元素 ai (1 ≤ i ≤ n)。

如果 ai  =  ?,则 Arthur 序列的第 i 个元素将被替换为问号。

否则,ai (- 109 ≤ ai ≤ 109) 是 Arthur 序列的第 i 个元素。

输出

如果 Arthur 在某些时候错了,并且没有适合给定信息的序列,则打印单个字符串“不正确的序列”(不带引号)。

否则,打印 n 个整数——Arthur 最喜欢的序列。如果有多个这样的序列,则打印具有最小和|ai|的序列,其中|ai|是ai的绝对值。如果仍有多个这样的序列,则允许您打印其中任何一个。打印序列的元素,不带前导零。

示例

输入 #1

3 2
? 1 2

输出 #1

0 1 2

输入 #2

5 1
-10 -9 ? -7 -6

输出 #2

-10 -9 -8 -7 -6

输入 #3

5 3
4 6 7 2 9

输出 #3

Incorrect sequence