You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

最短路径（$\texttt{path}$）

【题目描述】

小 D 有一张 $n+1$ 个点的图，点的标号为 $0\sim n$，对于所有 $1\le i\le n$，有一条 $i-1\to i$ 的有向边，初始该边边权为 $a_i$。

小 D 会进行 $q$ 次实验，每次实验为如下两种形式之一：

• 修改实验：将 $x-1\to x$ 的有向边边权增加 $w$。

• 查询实验：小 D 会选定一个范围 $[l,r]$，然后仅保留编号在这个范围内的点。

  他想选定一条路径，其起点和终点 $s,t$ 满足 $l\le s\le t\le r$，使得 $s\to t$ 的距离最短。

  但小 C 还有进一步的要求，他想知道这个区间内前 $k$ 短的路径长度，两条路径不同当且仅当 $s$ 或 $t$ 不同。

【输入格式】

从 $\texttt{path.in}$ 中读入数据。

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_1\sim a_n$。

接下来 $q$ 行，每行表示一个操作：

• 如果该实验是修改实验，输入 $1\ x\ w$。
• 如果该实验是查询实验，输入 $2\ l\ r\ k$。

【输出格式】

输出到 $\texttt{path.out}$ 中。

对于每次操作二，输出 $k$ 行，第 $i$ 行一个整数表示当前范围内第 $i$ 短的路径长度。

【样例 1 输入】

6 6
1 0 3 1 -4 3
2 4 6 3
2 1 6 2
1 1 -2
1 5 2
1 4 1
2 0 3 3

【样例 1 输出】

-4
-1
0
-4
-3
-1
-1
0

【样例 1 解释】

对于第一次查询实验，前 $3$ 短路径是 $4\to 5,4\to 6,4\to 4$。

对于第二次查询实验，前 $2$ 短路径是 $4\to 5,3\to 5$。

对于第三次查询实验，前 $3$ 短路径是 $0\to 1,0\to 2,0\to 0$。

【样例 2】

见下发文件中的 $\texttt{path2.in}$ 与 $\texttt{path2.ans}$。

该样例满足子任务 $3$ 的限制。

【样例 3】

见下发文件中的 $\texttt{path3.in}$ 与 $\texttt{path3.ans}$。

该样例满足子任务 $4$ 的限制。

【样例 4】

见下发文件中的 $\texttt{path4.in}$ 与 $\texttt{path4.ans}$。

该样例满足子任务 $5$ 的限制。

【样例 5】

见下发文件中的 $\texttt{path5.in}$ 与 $\texttt{path5.ans}$。

该样例满足子任务 $6$ 的限制。

【数据范围】

对于所有的测试数据有：$1\le n,q,k,\sum k\le 2\times 10^5,0\le l\le r\le n,-10^6\le a_i,w\le 10^6$。

保证每次询问时给定范围内至少存在 $k$ 条不同的路径。