Description

A company provides services to its partners located in different towns. The company currently has $3$ mobile service workers. If a service request occurs at some location, a worker must move from their current location to the request location (if no worker is already there) to fulfill the request. At any time, only one worker may move. They can move only when requested, and multiple workers are not allowed to be in the same location. Moving a worker from location $p$ to location $q$ incurs a certain cost $C(p,q)$. The cost is not necessarily symmetric, but staying still costs $0$, i.e., $C(p,p)=0$. The company must handle the received requests strictly in first-come-first-served order.
Please write a program that decides which worker should move for each request, so that the total cost of serving the given list of requests is as small as possible.

Input Format

The first line contains two integers $L$ and $N$. $L$ is the number of locations, and $N$ is the number of requests. Locations are represented by integers from $1$ to $L$. Each of the next $L$ lines contains $L$ non-negative integers. The $j$-th number in line $i+1$ is the cost $C(i,j)$. The last line contains $N$ integers, the list of requests. Each request is identified by the location where it occurs. Initially, the three service workers are at locations $1, 2,$ and $3$, and these are also used as the identifiers of the three workers.

Output Format

The first line contains an integer $M$, the minimum total cost to serve the list of requests. The second line contains exactly $N$ integers. The $i$-th number is the identifier of the worker ($1, 2$ or $3$) who will serve the $i$-th request.

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1

5
1 2 1 2 2 1 3 1 3 

Hint

Constraints

For $100\%$ of the testdata, $3 \leq L \leq 200$, $1 \leq N \leq 1000$, $C(i,j) < 2000$.

Notes

From Mobile Service, CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005.
Translated and organized by

Translated by ChatGPT 5