CF775A.University Schedule

In this problem your task is to come up with a week schedule of classes in university for professors and student groups. Consider that there are 6 educational days in week and maximum number of classes per educational day is 7 (classes numerated from 1 to 7 for each educational day).

It is known that in university n students study, m professors work and there are a classrooms for conducting classes. Also you have two-dimensional array with n × m size which contains the following information. The number which stays in i-th row and j-th column equals to the number of classes which professor j must conduct with the group i in a single week. The schedule which you output must satisfy to array described above.

There are several other conditions for schedule. Single professor can not conduct more than one class. Similarly, single student group can not be on more than one class at the same time.

Let define a fatigue function for professors and student groups. Call this function f.

To single professor fatigue calculated in the following way. Let look on classes which this professor must conduct in each of the 6-th educational days. Let x be the number of class which professor will firstly conduct in day i and let y — the last class for this professor. Then the value (2 + y - x + 1)·(2 + y - x + 1) must be added to professor's fatigue. If professor has no classes in day i, nothing is added to professor's fatigue.

For single student group fatigue is calculated similarly. Lets look at classes of this group in each of the 6 educational days. Let x be the number of first class for this group on day i and let y — the last class for this group. Then the value (2 + y - x + 1)·(2 + y - x + 1) must be added to this group's fatigue. If student group has no classes in day i, nothing is added to group's fatigue.

So the value of function f equals to total {fatigue} for all n student groups and for all m professors.

Your task is to come up with such a schedule which minimizes the value of function f.

Jury prepared some solution of this problem. For each test you will get a certain number of points. It equals to result of division of the value of function f from the jury solution by the value of function f for schedule which your program output (i. e. the smaller value of {fatigue} function your program find the more points you will get), multiplied by 100. In the other words if the value of f for jury solution equals to p and for your solution — to q, you will get 100·p / q points (note, that the number of points is a real number). The points will be added together for all tests. The goal is to score as many points as possible.

本题中，你的任务是为大学的教师与学生班级制定一份周课程表。假定每周有 6 个教学日，每个教学日最多安排 7 节课（每教学日的课时编号为 1 至 7）。

已知大学共有 $n$ 名学生、$m$ 名教师，以及 $a$ 间可用于授课的教室。此外，你将获得一个大小为 $n \times m$ 的二维数组，其内容如下：第 $i$ 行第 $j$ 列的数值表示教师 $j$ 在一周内需为学生班级 $i$ 授课的课时数。你所输出的课程表必须严格满足该数组所描述的要求。

课程表还需满足若干其他约束条件：

• 同一教师在任一时刻不能同时讲授多门课；
• 同一学生班级在任一时刻不能同时参加多门课。

我们定义一个针对教师与学生班级的“疲劳度”函数，记作 $f$。

教师疲劳度的计算方式如下：
考察某位教师在全部 6 个教学日内所承担的课程。对第 $i$ 个教学日，设该教师在该日最早授课的课时编号为 $x$，最晚授课的课时编号为 $y$，则向该教师的疲劳度累加值 $(2 + y - x + 1) \cdot (2 + y - x + 1)$；若该教师在第 $i$ 日无课，则不增加任何疲劳度。

学生班级疲劳度的计算方式类似：
考察某学生班级在全部 6 个教学日内所上的课程。对第 $i$ 个教学日，设该班级在该日最早上课的课时编号为 $x$，最晚上课的课时编号为 $y$，则向该班级的疲劳度累加值 $(2 + y - x + 1) \cdot (2 + y - x + 1)$；若该班级在第 $i$ 日无课，则不增加任何疲劳度。

因此，函数 $f$ 的取值等于所有 $n$ 个学生班级与所有 $m$ 位教师的疲劳度之和。

你的任务是构造一个使函数 $f$ 取值最小的课程表。

评委会已预先准备了本题的一个参考解法。对于每个测试用例，你将获得一定分数，其计算方式为：

$$\frac{\text{评委会参考解的 } f \text{ 值}}{\text{你程序输出解的 } f \text{ 值}} \times 100$$

即：你程序找到的 $f$ 值越小，得分越高（注意：得分为实数）。各测试用例的得分将累加，目标是尽可能获得高分。

The first line contains three integers n, m and a (1 ≤ n, m, a ≤ 60) — the number of groups, the number of professors and the number of classrooms.

Each of the following n lines contains m integers from 0 to 24 — j-th number in i-th line equals to the number of classes with the professor j must conduct with the i-th student group.

It is guaranteed that the number of classes in week for each professor and for each student group does not exceed 24. Also guaranteed that the total number of classes in week does not exceed 75% from a maximum number of classes which can be conducted based on the number of classrooms. For all tests there is at least one schedule satisfying all described conditions.

第一行包含三个整数 $n$、$m$ 和 $a$（$1 \leq n, m, a \leq 60$）——分别表示学生组的数量、教授的数量以及教室的数量。

接下来的 $n$ 行中，每行包含 $m$ 个整数，取值范围为 $0$ 到 $24$；其中第 $i$ 行的第 $j$ 个数表示第 $j$ 位教授需为第 $i$ 个学生组讲授的课时数。

保证每位教授每周授课总课时数以及每个学生组每周总课时数均不超过 $24$。同时保证每周总课时数不超过基于教室数量所能安排的最大课时数的 $75\%$。对于所有测试用例，至少存在一个满足上述所有条件的课程表。

In the first line print the minimized value of function f.

After that print blank line.

After that print the schedule for each student group in increasing order of group number. For each student group print 7 lines. Each line must contains 6 numbers. Let the number at i-th line and j-th column equals to x. If in j-th day current group has no class number i, x must be equals to zero. Otherwise x must be equals to the number of professor who will conduct the corresponding class with the corresponding student group.

The number of classes which will be conducted simultaneously must not exceeds the number of classrooms a.

Separate the description of the schedules for groups with a blank line.

第一行输出函数 $f$ 的最小化值。

之后输出一个空行。

之后按学生组编号升序依次输出每个学生组的课表。对每个学生组，输出 7 行，每行包含 6 个数字。设第 $i$ 行第 $j$ 列的数字为 $x$：若当前学生组在第 $j$ 天没有第 $i$ 节课，则 $x$ 必须为 0；否则 $x$ 必须为负责该课程（对应学生组）的教授编号。

同时进行的课程总数不得超过教室数量 $a$。

不同学生组的课表之间用一个空行分隔。

During the main part of the competition (one week) you solution will be judged on 100 preliminary tests. The first 10 preliminary tests are available for download by a link http://assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz.

After the end of the contest (i.e., a week after its start) the last solution you sent (having positive score) will be chosen to be launched on the extended final tests.

在比赛主体阶段（为期一周）中，您的解决方案将在 100 个初步测试用例上进行评测。前 10 个初步测试用例可通过以下链接下载：http://assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz。

比赛结束后（即自比赛开始起一周后），您提交的最后一个得分（分数为正）的解决方案将被选中，在扩展的最终测试用例上运行。