题目背景

EC-Final 赛场上，志愿者们正在为过题的队伍派发气球。Jiangrc 学长作为特别巡视员，发现场馆里各片区域的队伍获得的气球数量参差不齐，这让他觉得“不够美观”。 场馆内的队伍排成了一排，总共有 $N$ 支队伍。Jiangrc 手里有某种特权，可以向组委会申请 $M$ 次“区域空投”。 每次空投，他可以选择恰好连续的 $W$ 支队伍，让这些队伍的桌面上都增加 $1$ 个气球。 为了照顾那些气球最少的队伍，Jiangrc 希望在用完至多 $M$ 次空投后，全场气球数量最少的那支队伍拥有的气球数尽可能多。

题目描述

给定一个长度为 $N$ 的数组 $A$，表示每支队伍初始的气球数量。 你可以进行最多 $M$ 次操作。每次操作可以选择一个长度恰好为 $W$ 的连续子数组，将其中所有元素的值加 $1$。 求在最优策略下，操作完成后数组中最小值的最大可能值。

输入格式

第一行包含三个整数 $N, M, W$（$1 \le W \le N \le 10^5$，$1 \le M \le 10^9$）。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le 10^9$）。

输出格式

第一行包含三个整数 $N, M, W$（$1 \le W \le N \le 10^5$，$1 \le M \le 10^9$）。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le 10^9$）。

样例

5 3 2
1 2 1 3 2

2

样例解释

位置 1 需加 1，选 [1, 2]，剩余 2 次。数组：2 3 1 3 2

位置 3 需加 1，选 [3, 4]，剩余 1 次。数组：2 3 2 4 2 此时最小值已为 2。答案为 2。