一家公司为其位于不同城镇的合作伙伴提供服务。该公司有三名移动服务员工。如果某个地点出现了请求，服务人员中的一名必须从其当前位置移动到请求发生的地点（如果该地点尚无员工）以满足该请求。在任何时刻只能有一名员工移动。他们只能在有请求时移动，且不允许处于同一地点。将一名员工从位置 $p$ 移动到位置 $q$ 会产生给定的成本 $C(p,q)$。成本函数不一定是对称的，但原地不动的成本为 $0$，即 $C(p,p)=0$。公司必须严格按照先来后到的顺序满足收到的请求。目标是最小化完成给定请求序列的总成本。

任务

你需要编写一个程序，决定对于每个请求应派遣哪位服务员工去执行，使得完成给定请求序列的总成本尽可能小。

输入格式

输入文件的第一行包含两个整数 $L$ 和 $N$。$L$ ($3 \le L \le 200$) 是地点的数量，$N$ ($1 \le N \le 1000$) 是请求的数量。地点由 $1$ 到 $L$ 的整数标识。接下来的 $L$ 行，每行包含 $L$ 个非负整数。第 $i+1$ 行的第 $j$ 个数是成本 $C(i,j)$，且该值小于 $2000$。最后一行包含 $N$ 个整数，即请求列表。请求由发生该请求的地点标识符来标识。初始时，三名服务员工分别位于位置 $1$、$2$ 和 $3$。

输出格式

输出文件的第一行包含一个整数 $M$，即完成输入请求序列的最小总成本（子任务 A）。第二行包含恰好 $N$ 个整数。第 $i$ 个数是执行第 $i$ 个请求的服务员工标识符（$1$、$2$ 或 $3$）（子任务 B）。如果存在多种可能性，你的程序只需输出其中一种即可；输出哪一种均可。如果你只解决子任务 A，可以省略第二行。

样例

输入 1

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

输出 1

5
1 2 1 2 2 1 3 1 3