你负责管理一组工人，他们正在进行一个极其机密的工程项目。他们每个人都单独住在图 1 左侧所示的一组公寓中，每天早上他们同时出发，前往右侧所示的工作站之一。为了从住处到达工作站，他们必须通过中间的安全门。每个门都有两条不同的走廊可供使用，分别标记为 A 和 B。如图所示，每个门的 A 走廊始终位于 B 走廊的北侧。

图 1：公寓、门和工作站的布局。

让工人们到达工作站听起来很简单，但随着 COVID-19 的爆发，出现了一个问题。首先，由于社交距离限制，没有两个工人可以使用同一个门。其次，由于门的布局原因，如果一名工人使用了 A 走廊，那么使用其北侧门的工人就不能使用 B 走廊——因为距离太近了。如果一名工人使用了 B 走廊，也会发生类似的情况——使用其南侧门的工人不能使用 A 走廊。

你负责将工人分配到工作站，每个工作站分配一名工人。分配给哪个工作站并不重要，但你希望在遵守上述社交距离要求的同时，最小化所有工人行进的总距离。由于门的出入口布局特殊，使用 A 走廊和 B 走廊的距离有时会有很大差异，这使问题变得复杂。给定所有相对距离，确定一种工人到工作站的分配方案，使得所有人行进的总距离最小。

输入格式

输入的第一行包含一个正整数 $n \le 50$，表示工人、门和工作站的数量，编号均为 1 到 $n$。接下来有 $n$ 行，每行包含 $2n$ 个正整数。第 $i$ 行给出了工人 $i$ 到 $n$ 个门入口的距离；前两个值是到门 1 的 A 和 B 走廊的距离，接下来的两个值是到门 2 的 A 和 B 走廊的距离，依此类推。之后还有 $n$ 行，每行包含 $2n$ 个正整数。第 $j$ 行给出了工作站 $j$ 到 $n$ 个门出口的距离，格式与上述类似。所有距离均为正整数且 $\le 1\,000$。

输出格式

第一行输出可以达到的最小总距离。接下来输出 $n$ 行，显示每个工人的分配方案。第 $i$ 行的格式为 $i\ g_i\ w_i$，表示工人 $i$ 使用门 $g_i$ 前往工作站 $w_i$。请使用样例输出中的格式。如果存在多种最优分配方案，接受其中任何一种即可。

样例

样例输入 1

3
75 64 25 9 32 1
72 51 49 46 64 53
13 37 75 35 62 50
90 62 72 6 30 35
39 89 17 62 47 65
94 79 27 93 21 58

样例输出 1

163
1 3B 3
2 2B 1
3 1A 2