Bajtazar 是 Bajtokom 的老板，这是 Bajtocja 最大的 IT 解决方案供应商。公司目前正面临严重的财务问题。拯救 company 免于破产的唯一机会是赢得一个“非常重要项目”的招标，并（不幸地）大规模裁减许多员工。招标评估的主要标准显然是所提出的最低价格。

问题在于，执行该项目需要员工，因此不能裁掉所有人，这意味着必须支付某些人的工资。Bajtazar 将所有员工排成一长队。经过仔细分析，他决定需要组建几个员工团队。每个团队都从队列的连续片段中选出，并且必须至少包含一定数量的员工。Bajtazar 了解每位下属的薪资要求，他希望确定留下哪些员工，以便在能够完成项目的同时，使工资成本尽可能低。

显然，选择 these 员工的任务就交给你了。为了简化你的任务，Bajtazar 设定的团队结构满足以下条件：对于任意两个团队，它们选择员工的片段要么是不相交的，要么是一个完全包含在另一个之中。被雇佣的员工可以同时在任意多个团队中工作（并且只需要支付一次工资！）。

帮助 Bajtazar 拯救公司！

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示员工人数。员工按队列中的顺序从 $1$ 到 $n$ 编号。

第二行包含 $n$ 个整数 $c_i$ ($1 \le c_i \le 10^9$)，其中第 $i$ 个数表示第 $i$ 位员工的薪资要求。

第三行包含一个整数 $m$ ($1 \le m \le 200\,000$)，表示完成项目所需的团队数量。接下来的 $m$ 行包含各团队的描述；第 $j$ 行包含三个整数 $s_j, t_j, p_j$ ($1 \le s_j \le t_j \le n, 1 \le p_j \le t_j - s_j + 1$)，表示第 $j$ 个团队应由从第 $s_j$ 位到第 $t_j$ 位员工（含）的连续片段中选出的至少 $p_j$ 名员工组成。

你可以假设输入中给出的所有连续片段都是两两不同的；更正式地说，对应于团队的有序数对 $(s_j, t_j)$ 是两两不同的。此外，对于输入中的任意两个片段，它们要么是不相交的，要么是一个完全包含在另一个之中。

输出格式

你的程序应在第一行输出一个整数——所选员工的最低工资成本。

在第二行和第三行，输出该成本下的一份员工名单示例：第二行输出这些员工的数量 $p$ ($1 \le p \le n$)，第三行输出这 $p$ 位员工的编号。

如果存在多个正确的答案，你的程序可以输出其中任意一个。

样例

输入格式 1

8
15 8 2 20 4 9 3 10
4
1 8 5
2 4 2
5 6 1
5 8 2

输出格式 1

26
5
2 3 6 5 7

说明

样例解释：下图展示了样例测试的最优解。圆圈内为 Bajtazar 雇佣的员工。

评分

测试点被分为以下子任务。每个子任务的测试点由一个或多个独立的测试点组组成。

如果你的程序仅在第一行输出了正确的最低工资成本，但给出的员工名单与该成本不符，你将获得该测试点 50% 的分数。

反馈测试（ocen）：

• 1ocen：$n = 5, m = 6$；答案为 $9$ 的简单测试；
• 2ocen：$n = 20, m = 5$；员工的薪资要求是 $1$ 到 $20$ 的排列；
• 3ocen：$n = 1000, m = 200$；对于 $1 \le i \le n$ 满足 $c_i = ((i - 1) \bmod 10) + 1$，且对于 $1 \le j \le m$ 满足 $s_j = 5j - 4, t_j = 5j, p_j = 1$；
• 4ocen：$n = 200\,000, m = 200\,000$；对于 $1 \le i \le n$ 满足 $c_i = 1$，且对于 $1 \le j \le m$ 满足 $s_j = 1, t_j = j, p_j = \min(j, 50)$。