Problem Background

Steve successfully activated the mechanism and discovered a massive maze behind it.

Problem Description

The maze consists of $n$ caves, connected by numerous one-way tunnels, making it difficult to count them all.

However, upon analysis, it was found that:

These tunnels can be grouped into $m$ sets. For each set, every cave within the range $[s_l, s_r]$ is connected to every cave within the range $[t_l, t_r]$ by a tunnel. Each set contains $(s_r - s_l + 1) \cdot (t_r - t_l + 1)$ tunnels, and the time to traverse each tunnel within the same set is equal.

To further save time, Steve can dig new tunnels.

However, the nature of each cave varies, making some caves impossible to dig tunnels from.

Specifically, the $i$-th cave has a value $v_i$, where $v_i = 0$ indicates that no tunnel can be dug from this cave. For other values, it indicates the time required to dig a tunnel from the $i$-th cave to the $j$-th cave and reach the $j$-th cave, which is $|i - j| \cdot v_i$.

Steve aims to reach the $n$-th cave in the shortest time possible and decides not to limit the number of tunnels dug.

Now, you need to tell Steve the minimum time required. If possible, you should help Steve find an optimal plan.

Input Format

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers $v_1, v_2, ..., v_n$.

The following $m$ lines describe each tunnel set.

Each line contains five integers $s_l, s_r, t_l, t_r, w$, where $w$ represents the traversal time.

Output Format

If there is no solution, output a single integer "-1" (without quotes) on the first line.

If there is a solution, output as follows:

The first line contains an integer $t$, representing the minimum time required.

If you cannot provide a plan, output a single integer $0$ on the second line.

If you can provide a plan, output an integer $c$ on the second line, followed by $c$ integers on the third line, representing the sequence of cave numbers in an optimal plan.

You do not need to inform Steve whether the tunnels are dug or which set they belong to.

Sample Input and Output

Sample Input #1

6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

Sample Output #1

9
3
1 2 6

Sample Input #2

6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

Sample Output #2

9
4
1 3 4 6

Notes

Sample 1: From cave 1 to cave 2 using the first set of tunnels, and from cave 2 to cave 6 by digging a tunnel, taking $1 \cdot (6 - 2) = 4$ time.

Sample 2: From cave 1 to cave 3 using the first set of tunnels, from cave 3 to cave 4 by digging a tunnel, taking $2 \cdot (4 - 3) = 2$ time, and from cave 4 to cave 6 using the second set of tunnels.

Each Subtask includes two test cases, with the lower score taken.

For each test case:

If the output format is incorrect, the test case scores 0 points.

If the correct time is not provided, the test case scores 0 points.

If the correct time is provided but no plan is given, you can get half the points for the test case (rounded down).

If an incorrect plan is provided, you may get half the points for the test case, or 0 points.

If a correct plan is provided, you can get full points for the test case.

Both outputs above can get full points, and another plan is $1 2 4 6$.

If you output:

9
0

You can get half the points for the test case.

Data Range

$1 \le w, v_i \le 10^9$

Special Property 1: All $v_i = 0$

Special Property 2: All $v_i \in \{0, k\}$, where $k$ is a constant

Special Property 3: All $s_l = s_r, t_l = t_r$

It is guaranteed that there exists a plan to reach the $n$-th cave.

Regarding incorrect plans:

If the output has $2 \leq c \leq n$, starts with 1, ends with $n$, and the intermediate points are integers between $(1, n)$, this solution may be an optimal solution and can get half the points.

Otherwise, it scores 0 points.

Do not worry about the spj timing out or running out of memory

见题面 Input 部分

见题面 Output 部分