Warp Speed II

Input

Input is a standard input which consists of $4$ parts, separated by a blank line.

The first part defines the sizes of warp-drive states and hop types.

• It contains only one line. This line contains $2$ numbers separated by a space. These $2$ number are

  • Size of warp-drive states ($N$), which is between $1$ and $100$.

    • The state id is starting from $0$ to N-1.

    • The first state (id $\#0$) is the idle state. At this and only this state, the warpdrive can't perform any hop. (It is the default starting and ending state for any output state sequence.)

  • Size of different types of hops ($H$), which is between $1$ and $1000$.

    • The hop id from $0$ to H-1.

The second part is a table showing the energy for switching warp-drive states. The table size is $N$ rows and $N$ columns, which contains N^2 energy values.

• There are $N$ lines. Each line contains N energy values. These values are between $1$ and $100$.

• Each energy value can be indexed by its row and column. The row and column indexes are the state ids of the current and next warp-drive states respectively. Please be notified that these two indexes are starting from $0$.

  • For example, the value at (row index, column index) = ($5$,$0$) is the energy for switching warp-drive state from number $5$ to $0$. (This value is the first number in the sixth line.)

The third part is a table showing the energy consumption in performing hops for each state drive.

The table size is $N$ rows and $H$ columns, which contains $N$ by $H$ values.

• There are $N$ lines. Each line contains $H$ energy values. These values are between $1$ and $100$.

• Each energy value can be indexed by its row and its column. The row index is the id of the current warp-drive state. The column index is the id of the hop. Please be notified that these two indexes are starting from $0$.

  • For example, the value at (row index, column index) = ($1$,$9$) is the energy for warp-drive at state $\#1$ to perform hop $\#9$. (This value is the tenth number in the second line.)

  • Please be notified that in the very first line of this part, which corresponds to the state $\#0$ or the idle state, all numbers are zeros. This rather means that it can't perform any hop in this state.

The fourth part is a set of hop sequences. The number of sequences in this set is between $1$ and $1000$.

• The number of lines is $1$ up to $1000$.

• Each line in this part contains one hop sequences.

• The number of hops in a sequence is between $1$ and $1000$.

• Each hop is a number (starting from $0$ to H-1) and is separated with space.

The blank line after the fourth part is the termination of the input.

Output

For each hop sequence in the fourth part of the input, write $2$ parts of output as follows

• In the first line, write the total amount of energy which must be minimum.

• In the following line, write the solution. The solution contains a sequence of warp-drive states corresponds to the given hop sequence. (The size of input and output sequence must be equal.) If there are two or more possible solutions which consumes the same amount of energy, write only the sequence which contains the lowest states comparing from left to right.

More Explanations

There are $15$ lines in the sample input and $4$ lines in the sample output.

In the first sample output (solution for input line $\#13$), the minimum total energy is $9$. The warpdrive state sequence is $[32]$ or [0-\ 3\ 2\ -0]. There are $3$ state switchings from $0$ → $3$, $3$ → $2$, and $2$ → $0$, which consumes 1 + 1 + 2 = 4. And two hops ($0$ and $4$) at state $3$ and $2$ respectively, which consumes 4 +1 = 5. So the total energy is 4 + 5 = 9.

In the last sample output, the minimum energy is $23$. The solution is [0-\ 1\ 1\ 2\ 3\ -0] which draws $23$ energy in total.

Examples