这一篇题解中提到了一种不使用差分的做法，当然，把枚举 $k$ 的上界开到 $6000$ 是错的。

数据