在括号序列之后,亚瑟开始学习数论。他得到了一个新的最喜欢的长度为 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