暂无测试数据。

S 公司共设有 $N$ 个工位，将工位按照顺序编号为 $1\sim N$，每个工位均有一名员工，因此最初时有 $N$ 名员工。

现在有一个项目，这个项目至少需要一名员工完成。因为项目太过于繁琐，因此每名员工对于这个项目均有一个厌烦值，第 $i$ 名员工的厌烦值为 $a_i$。

万能的蒜头君通过某种 AI 算法模拟了项目的推进过程，模拟结果显示，项目会依次发生 $M$ 个事件，事件共分为两类：

1. 第 $x$ 个工位上的员工坚持不下去了，选择了辞职。这个时候公司新招来一名新的员工，该员工需要在第 $x$ 个工位上工作，他对于该项目的厌烦值为 $y$；
2. 第 $x$ 个工位上的员工太过于烦躁了，他就向领导提出要求：如果我参与工作，那么此时第 $l\sim r$ 工位上的员工也必须参与工作。

蒜头君的 AI 算法非常强大，预测的事件均正确。现在他需要在这些事件都发生完后选择某些员工，让他们参与该项目的最后冲刺工作，需要满足这些员工的厌烦值之和是所有方案中最小的情况。如果某些员工已经辞职了，但是还需要选择他时（比如单纯想选择他，亦或是需要满足事件 $2$ 中某名员工提出的要求），公司就会花费高薪重新将该员工招回来。

请你帮蒜头君计算所有的选择方案中，参与工作的员工的厌烦值之和的最小值。

请你帮蒜头君选择参与工作的员工，使得他们的厌烦值之和是所有方案中最小的情况，并输出这个厌烦值之和。

注意：

• 无论是最初的员工，还是事件 $1$ 中新招的员工，他们之间相互独立，互不相同。
• 工位是固定的，员工不固定；进行工作的是员工，而不是工位。

输入格式

第一行输入一个正整数 $N$，表示工位的数量。

第二行以空格隔开输入 $N$ 个非负整数 $a_i$，表示最初时，第 $i$ 名员工（他在第 $i$ 个工位）对于项目的厌烦值。

第三行输入一个正整数 $M$，表示 AI 算法预测的事件数量。

接下来 $M$ 行，每行先输入一个整数变量 $op$，表示事件的类型：

• 若 $op = 1$，则表示事件种类 $1$，还需要再输入两个整数 $x,y$，表示第 $x$ 个工位上的员工辞职了，新招来的员工对于项目的厌烦值为 $y$；
• 若 $op = 2$，则表示事件种类 $2$，还需要再输入三个正整数 $x, l, r$，表示：如果第 $x$ 个工位上的员工参与工作，那么此时第 $l\sim r$ 工位上的员工也需要参与工作。

输出格式

输出一个整数，表示所有方案中，最小的厌烦值之和。

数据范围

对于 $30\%$ 的数据，$1\leq N + \text{事件 1 中新招的员工数量} \leq 20, 0 \leq M \leq 50$；

对于另外 $30\%$ 的数据，$1\leq N + \text{事件 1 中新招的员工数量} \leq 10^5, 0 \leq M \leq 10^5, \sum(r - l + 1) \leq 10^5$；

对于 $100\%$ 的数据，$1\leq N + \text{事件 1 中新招的员工数量} \leq 10^5, 0 \leq M \leq 10^5, 1\leq x \leq N, 0 \leq a_i, y \leq 10^9, 1\leq l \leq r \leq N$；

5
1 10 100 1000 10000
4
2 1 3 4
2 3 5 5
1 3 0
2 3 1 2

10