Bajtazar is the boss of Bajtokom, the largest provider of IT solutions in all of Bajtocja. The company is currently facing serious financial problems. The only chance to save the company from bankruptcy is to win a tender for a Very Important Project and (unfortunately) to lay off many employees. The main criterion for evaluating tender bidders is, of course, the lowest proposed price.

The problem is that employees are necessary to carry out the project, so they cannot all be fired, and therefore someone will have to be paid. Bajtazar has lined up all employees in one long row. After careful analysis, he decided that it would be necessary to create several teams of employees. Each team of employees is selected from a contiguous segment of the row and must consist of at least a certain fixed number of employees. Bajtazar, knowing the salary requirements of each subordinate, would like to determine whom to keep in the company so that it is possible to carry out the project while keeping the salary cost as low as possible.

It is clear that the task of choosing these employees falls to you. To make your task easier, the team structure established by Bajtazar satisfies the condition that for any two teams, the segments from which their employees can be chosen are either disjoint or one is contained entirely within the other. A hired employee can work in any number of teams simultaneously (and you only need to pay them one salary!).

Help Bajtazar save the company!

Input

The first line of input contains a single integer $n$ ($1 \le n \le 200\,000$) representing the number of employees. Employees are numbered with consecutive numbers from $1$ to $n$ according to their order in the row.

The second line of input contains a sequence of $n$ integers $c_i$ ($1 \le c_i \le 10^9$) – the $i$-th number denotes the salary requirement of the $i$-th employee.

The third line of input contains a single integer $m$ ($1 \le m \le 200\,000$) representing the number of teams necessary to carry out the project. The next $m$ lines of input contain descriptions of the teams; the $j$-th of these lines contains three integers $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$), specifying that the $j$-th team must consist of at least $p_j$ employees chosen from the contiguous segment of the row from the $s_j$-th to the $t_j$-th employee (inclusive).

You may assume that all contiguous segments of the row given in the input are pairwise distinct; more formally, the ordered pairs of numbers $(s_j, t_j)$ corresponding to the teams are pairwise distinct. Additionally, for any two segments of the row in the input, they are either disjoint or one is contained entirely within the other.

Output

Your program should output on the first line a single integer – the minimum salary cost of the employees selected for the project.

On the second and third lines, you should output an example list of hired employees for such a cost: on the second line, the number $p$ of these employees ($1 \le p \le n$), and on the third line, a sequence of $p$ employee numbers. In case there is more than one correct answer, your program may output any of them.

Examples

Input 1

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

Output 1

26
5
2 3 6 5 7

Note

Explanation of the example: The image below shows the optimal solution for the sample test. Employees hired by Bajtazar are circled.

Subtasks

If your program outputs only the correct minimum cost on the first line, but the list of employees provided by you is not consistent with that cost, you will receive 50% of the points for the given test.

"Evaluation" tests: 1. $n = 5, m = 6$; a simple test with the answer 9; 2. $n = 20, m = 5$; employee requirements are a permutation of numbers from 1 to 20; 3. $n = 1000, m = 200$; $c_i = ((i - 1) \pmod{10}) + 1$ for $1 \le i \le n$ and $s_j = 5j - 4, t_j = 5j, p_j = 1$ for $1 \le j \le m$; 4. $n = 200\,000, m = 200\,000$; $c_i = 1$ for $1 \le i \le n$ and $s_j = 1, t_j = j, p_j = \min(j, 50)$ for $1 \le j \le m$.