Minimize Service Personnel Movement Cost

A company offers services to its partners located in different towns. The company has three mobile service personnel. When a service request occurs at some location, if there is no employee at that location then one of the employees must be moved from his current location to that location in order to serve the request. At any time only one employee can move. Employees move only when a request occurs and it is not allowed for two employees to be at the same location. Moving an employee from location \( p \) to location \( q \) incurs a cost \( C(p,q) \). The cost need not be symmetric, but the cost of not moving is always zero, i.e. \( C(p,p)=0 \). The company must serve the requests in a strict first-come-first-served order.

Your task is to write a program that, given a list of service requests, decides which service personnel (numbered 1, 2, and 3) should move to serve each request such that the overall cost is minimized.

Details: Initially, the three employees are located at positions 1, 2, and 3 respectively. The input provides the number of locations \( L \) and the number of requests \( N \), followed by an \( L \times L \) cost matrix. The \( j \)th number in the \( i \)th row of the cost matrix represents \( C(i,j) \). Finally, a sequence of \( N \) requests is given, where each request is represented by a location (an integer between 1 and \( L \)). If a request occurs at a location where an employee is already present, that employee will serve the request with no cost. Otherwise, exactly one employee must move from his current location to the requested location, incurring the corresponding cost.

inputFormat

The input consists of the following:

1. A line containing two integers \( L \) and \( N \) where \( L \) is the number of locations and \( N \) is the number of requests.
2. \( L \) lines follow, each containing \( L \) integers. The \( j \)th number in the \( i \)th line indicates the cost \( C(i,j) \) to move from location \( i \) to location \( j \). It is guaranteed that \( C(i,i)=0 \) for all \( i \).
3. A line with \( N \) integers representing the sequence of service requests. Each integer is a location (from 1 to \( L \)).

Note: The employees start at locations 1, 2, and 3 respectively.

outputFormat

Output two lines:

1. The first line contains a single integer representing the minimum total cost required to service all requests.
2. The second line contains \( N \) integers separated by spaces. The \( i \)th integer indicates the number of the employee (1, 2, or 3) who serves the \( i \)th request. If a request is made at a location where an employee is already present, output that employee's number.

sample

4 4
0 5 3 6
2 0 4 1
7 4 0 2
3 8 6 0
2 4 1 3

1
2 2 1 3