The competition is approaching, and Little D has decided to cram some algorithms.

There are $n$ algorithms to learn, labeled $1, 2, \dots, n$.

Little D has assigned a value to each algorithm based on its learning difficulty and practical utility. The value of algorithm $i$ is $w_i$.

Little D wants to learn all $n$ algorithms in some order. We can represent his learning sequence as a permutation $p$ of $1, 2, \dots, n$, where the $i$-th element $p_i$ is the index of the algorithm learned at step $i$.

Little D does not want the difference in value between consecutively learned algorithms to be too large. For a given learning sequence, he defines the cost as the sum of the absolute differences in value between adjacent algorithms. Formally, for a permutation $p$, the weight $w(p)$ is defined as:

$$w(p)=\sum_{i=1}^{n-1}\left \lvert w_{p_i}-w_{p_{i+1}} \right \rvert$$

However, Little D soon discovered some issues: some algorithms have dependencies, for example, learning LCT requires learning Splay first. Little D has divided these algorithms into two categories: basic algorithms and extended algorithms.

There are $m$ basic algorithms, which for convenience are labeled $1, 2, \dots, m$; the extended algorithms are the remaining $n-m$ algorithms, labeled $m+1, m+2, \dots, n$.

For each extended algorithm $i$ ($m+1 \le i \le n$), the algorithm depends on exactly one basic algorithm, denoted as $u_i$ ($1 \le u_i \le m$). That is, algorithm $i$ must be learned after algorithm $u_i$.

Little D wants to know, among all learning sequences $p$ that satisfy these dependencies, which one minimizes $w(p)$.

Since Little D has not started learning these $n$ algorithms yet, he cannot calculate this himself. Please help him find the minimum value of $w(p)$ and a permutation $p$ that achieves this minimum.

Input

The input is read from standard input.

The first line contains two space-separated integers $n$ and $m$, representing the total number of algorithms and the number of basic algorithms, respectively.

The second line contains $n$ space-separated integers, where the $i$-th integer $w_i$ represents the value of algorithm $i$.

The third line contains $n-m$ space-separated integers, where the $i$-th integer $u_{m+i}$ represents the index of the basic algorithm that the extended algorithm $m+i$ depends on.

Output

The output is written to standard output.

The first line contains an integer representing the minimum value of $w(p)$.

The second line contains $n$ space-separated integers, where the $i$-th integer $p_i$ represents the index of the algorithm learned at step $i$ in the optimal solution.

It can be proven that under the constraints of the problem, Little D can always learn all the algorithms; that is, a valid $p$ always exists. If there are multiple valid permutations $p$ that minimize $w(p)$, you may output any one of them.

Examples

Input 1

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

Output 1

7
2 3 1 4 5 6

Subtasks

For each test case, if your output $w(p)$ is correct, you will receive $60\%$ of the points for that test case.

Furthermore, if your output permutation $p$ is a valid sequence that achieves the minimum $w(p)$, you will receive the remaining $40\%$ of the points for that test case.

Please note that even if you only intend to obtain partial points for certain test cases, you must still strictly follow the output format.

For all test data, $1 \le n \le 10^{6}$, $1 \le m \le n$, $1 \le w_i \le 10^{12}$, $1 \le u_i \le m$ (for $m+1 \le i \le n$).

There are 7 subtasks in total. For each subtask, your score is the minimum score you obtained across all test cases within that subtask.

The special constraints for each subtask are shown in the table below: