该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

难度：NOI/CTSC T2-T3 级别
时间限制：2 秒
内存限制：512 MB

题目背景

奶龙发现了一片神奇的矿区，矿区是一个长度为 ( n ) 的线性序列，每个位置 ( i ) 有一个宝藏价值 ( a_i )。矿区被划分为若干段，每段称为一个“小小的坑”。奶龙每次会选择一段连续的坑 ( [l, r] )，用它的爪子“挖呀挖呀挖”，但奶龙的体力有限，每次只能挖最多 ( k ) 个坑（( k ) 为给定常数），且挖的坑必须满足价值单调不减（即 ( a_l \leq a_{l+1} \leq \dots \leq a_r )）。

奶龙希望找到总价值最大的挖法，即在所有合法的挖法中，最大化 ( \sum a_i )（被挖的坑的价值之和）。由于矿区会动态变化（例如宝藏价值被更新），你需要设计一个高效的数据结构支持以下操作：

1. 更新操作 Update x v：将 ( a_x ) 修改为 ( v )。
2. 查询操作 Query L R：查询区间 ( [L, R] ) 内，奶龙能挖出的最大总价值（需满足每次挖的坑数 ( \leq k ) 且单调不减）。

输入格式

• 第一行三个整数 ( n, m, k )（( 1 \leq n, m \leq 10^5 )，( 1 \leq k \leq 10 )），分别表示矿区长度、操作次数和每次最多挖的坑数。
• 第二行 ( n ) 个整数 ( a_1, a_2, \dots, a_n )（( 1 \leq a_i \leq 10^9 )），表示初始宝藏价值。
• 接下来 ( m ) 行，每行为以下两种格式之一：
  • Update x v：更新 ( a_x ) 为 ( v )（( 1 \leq x \leq n )，( 1 \leq v \leq 10^9 )）。
  • Query L R：查询区间 ( [L, R] ) 的最大挖宝价值（( 1 \leq L \leq R \leq n )）。

输出格式

对每个 Query 操作，输出一行答案。

样例输入

5 3 2  
3 1 4 1 5  
Query 1 5  
Update 2 2  
Query 1 5

样例输出

9  
12

样例解释

• 第一次查询：奶龙可以挖 ( [1,2] )（价值 3+1=4）和 ( [3,5] )（价值 4+1+5=10），但后者坑数 3 > ( k )，因此最优解为挖 ( [3,4] )（4+1=5）和 ( [5,5] )（5），总价值 5+5=10。但实际更优解是挖 ( [1,1]+[3,4]+[5,5] )（3+4+1+5=13），但需注意坑数限制和单调性。
  （注：此处需结合具体 ( k ) 和序列设计更严谨的样例，实际题目需保证答案唯一性。）