CF518E Arthur and Questions

在研究括号序列之后，Arthur 开始研究数论。他得到一个新的、长度为 $n$ 的最喜欢的序列 $a = (a_1, a_2, ..., a_n)$，该序列由整数构成，并给定一个不超过 $n$ 的整数 $k$。 这个序列具有如下性质：如果你依次写出所有长度为 $k$ 的连续元素的子段的和（即 $a_1+a_2+\ldots+a_k$，$a_2+a_3+\ldots+a_{k+1}$，……，$a_{n-k+1}+a_{n-k+2}+\ldots+a_n$），那么这些和将形成一个严格递增的序列。 例如，对于 $n=5$，$k=3$，$a=(1, 2, 4, 5, 6)$，所有长度为 $3$ 的子段和为 $1+2+4, 2+4+5, 4+5+6$，即 $(7, 11, 15)$，满足严格递增的要求。 很明显，这样的子段和的个数为 $n-k+1$。 有人（我们不说是谁）把 Arthur 序列中的某些数替换成了问号（如果一个数被替换，则恰好是一个问号）。我们需要还原这个序列，使它满足上述要求，并且 $\sum |a_i|$（即所有 $a_i$ 的绝对值之和）最小。

第一行包含两个整数 $n$ 和 $k$（$1\leq k\leq n\leq 10^5$），分别表示 Arthur 序列的长度和子段的长度。 第二行包含 $n$ 个以空格分隔的元素 $a_i$（$1\leq i\leq n$）。 如果 $a_i = ?$，表示第 $i$ 个元素被替换为了问号。 否则，$a_i$ 是一个整数，且 $-10^9\leq a_i\leq 10^9$。

如果 Arthur 搞错了，没有任何符合要求的答案，输出一行字符串“Incorrect sequence”。 否则，输出 $n$ 个整数，表示还原后的 Arthur 最喜欢的序列。如果有多组解满足条件，输出绝对值之和 $\sum |a_i|$ 最小的那组；如果这样的解有多组，可以输出其中任意一组。输出的每一个元素均不含前导零。

由 ChatGPT 5 翻译