火车站

题目描述

在某火车站里，从左至右依次排列有 n 个站台。第 i 个站台有 ai 个人正在候车。

在接下来的 t 个时刻里，有 m 列火车将会停靠在本站。由于火车很长，每列火车会占据一段连续的站 台。具体而言，第 i 列火车在停靠时将会占据编号在 [li , ri] 之间的站台。每列火车只会选择 t 个时刻中 的一个时刻停靠。

你是该站的火车调度员。你要合理安排每列火车在哪个时刻停靠（也可以让某列火车不停靠，直接开 走），使得： 每个时刻停靠的所有火车占据的站台集合互不相交（不同时刻之间没有干扰）。

· 最大化上车的总人数。如果第 i 个站台在 t 个时刻中的任何一个时刻有火车停靠，则该站台上的 ai 个人都会上车。在 t 个时刻内不会有更多的人来到该站台（即来到此的第二列火车不会接到人）。

但你并不确定 t 的值是多少，并且在你回忆当天的火车时刻表的时候，站台上的人数与火车的停靠情况 又发生了新的变化。具体而言，可能发生以下三种修改： · 第 i 个站台上的人数变为了 x。由于这是一个实际问题，保证任意时刻站台上的人数非负。 第 i 列火车改变了行程，不能在本站停靠。保证在此之前第 i 列火车可以在本站停靠。

新增一列在本站停靠的火车，编号为 m + 1，停靠区间为 [l, r]。然后将 m 加一。 现在你回忆起了 t 的最大可能值 T。你想知道，对于 1 ≤ i ≤ T ，在前 i 次修改结束后，如果实际停 靠时刻数 t = i，那么最多可以接到多少人。询问相互独立，即并不会真实地改变人数。

另外，由于你无法预料到接下来会发生哪些修改，你又想在每次修改之后快速求出答案，因此本题强制 在线。

输入格式

第一行三个整数 n ，m ，T。

接下来一行 n 个整数 ai，表示初始站台人数。

接下来 m 行，每行两个整数 l, r，表示初始第 i 列火车的停靠位置。

接下来 T 行，每行表示一次修改，格式如下：

· 1 k x 表示将 ak 修改为 x。

· 2 i 表示第 i 列火车将不能在本站停靠。保证 i 列火车此前可以在本站停靠，且 i ≤ m。 · 3 l r 表示将 m 加一，然后新增一列火车，停靠在 [l, r]，编号为 m。

记 lastans 为上一次询问的答案，初始时 lastans = 0。所有修改的参数（不包括 op）均需要异或 lastans 以得到真实参数。

输出格式

共 T 行，每行一个整数 ansi，表示经过前 i 次修改之后， t = i 时的答案。

样例

样例 1 输入

5 2 2

1 2 3 4 5

1 3

2 4

1 4 0

3 5 3

样例 1 输出

6

11