512 「LibreOJ NOI Round #1」春游

小 C 管理着一个很大的动物园，这个动物园有许许多多奇奇怪怪的小动物。不过他们都有一个共同的特点，就是非常喜欢春天。于是，为了提高动物园的和谐程度，小 C 决定带小动物们出去春游。

不过，春游是一件非常麻烦的事情。每个小动物都会带来一定的麻烦程度；更麻烦的是，特定的小动物待在一起会有特殊的麻烦程度变化。比如，跳蚤国王和蛐蛐国王待在一起，事情就麻烦了，因为蛐蛐国王总是想把跳蚤国王的子民们分割开来；而花鸡和青蛙待在一起，却可以使气氛更加的活跃，因为他们经常在一起讨论关于眼镜的保养问题，谈笑风生间时间很快就过去了，自然管理起来就不那么麻烦。

由于小动物实在是太多了，小 C 决定分批次带小动物们出去春游。为了方便管理，每次春游时小 C 会选出 $M$ 个队长，来管理这次参与春游的其他 $N$ 位小动物。其中，第 $i$ 位队长的麻烦程度是 $b_i$，第 $i$ 个小动物的麻烦程度是 $a_i$。队长以身作则，答应了小 C 他们和其他小动物的麻烦程度不会发生特殊变化；所以所有的变化都是在 $N$ 位小动物之间发生的。经过小 C 调查，一共有 $K$ 对小动物存在着能够导致变化的友谊/矛盾，形式化地讲有两种：

1. $u_i$ 和 $v_i$ 在一个小队时，这个小队的麻烦程度会增加 $w_i$；
2. $u_i$ 和 $v_i$ 在一个小队时，这个小队的麻烦程度会乘以 $w_i$。

当方案确定后，所有 1 类型的变化先生效，然后所有 2 类型的变化依次生效。（也就是说，1 类型变化增加的值同样会被 2 类型变化乘上系数，并且系数是连乘起来的）

形式化地说，对于一个小队 $S={B,A_1,A_2,...,A_k}$（其中队长是 $B$），$S$ 的麻烦程度为 $\prod_{u_{2,i}\in S,v_{2,i}\in S} w_{2,i}(b_B+\sum_{i=1}^k a_{A_i}+\sum_{u_{1,i}\in S,v_{1,i}\in S} w_{1,i})$（其中下标 $(1,i)$ 表示第一种变化的第 $i$ 个，下标 $(2,i)$ 表示第二种变化的第 $i$ 个）。

现在小 C 想分 10 次带小动物们出去春游，她想最小化每次春游麻烦程度最大的小队的麻烦程度。她找到了你来帮他解决这个问题，你能给她尽量优秀的方案么？

本题为提交答案题。所有输入数据 spring1.in ~ spring10.in 见附加文件下载，分别对应 10 次春游的情况，选手文件见题目描述上方附加文件。

对于每组输入数据：

第一行是三个空格隔开的正整数，分别是 $N,M,K$，即待分配队员数，小队数，以及特殊变化数。

第二行是 $N$ 个非负整数，第 $i$ 个数表示 $a_i$，即待分配的第 $i$ 位队员的麻烦程度。

第三行是 $M$ 个非负整数，第 $i$ 个数表示 $b_i$，即第 $i$ 位队长的麻烦程度。

第四行起共 $K$ 行，每行格式为以下两种中的一种：

1. $1\ u_i\ v_i\ w_i$ 表示一种加的特殊变化；
2. $2\ u_i\ v_i\ w_i$ 表示一种乘的特殊变化。

其中有$1 \leq u_i \lt v_i \leq N$。

输出文件为 spring1.out ~ spring10.out，分别对应相应的输入文件。

对于每个输出文件，请输出 $2M$ 行：

第 $2i - 1$ 行，请输出一个非负整数 $c_i$，表示你的方案里，有 $c_i$ 个小动物被分配到了第 $i$ 个小队；

第 $2i$ 行，请输出 $c_i$ 个正整数 $d_{i, j}$，第 $j$ 个表示分配到这个队伍的小动物标号 $d_{i, j}$。如果 $c_i = 0$，请输出一个空行。

你可以认为，你的答案如果能被下发的 checker 接受，那么就能够被评测程序接受。

你可以在你的输出文件的第 $2M + 1$ 行后输出任意额外的内容；如果你有兴趣的话，我们希望你能把你的解法写在答案后面。

如果第 $4$ 组条件不生效，那么不含队长时答案将一定不会低于 $16$；

如果第 $4$ 组条件生效，此时若第$3$组条件生效，那么不含队长时答案一定不会低于 $(4 + 8 + 16) \times 1.5 \times 0.5 = 21$；

如果第 $4$ 组条件生效，第$3$组条件不生效，那么剩余情况有： 1. ${{3}, {1, 2, 4}}:\ $最优方案为 $\mathrm{max}(8 + 9, (2 + 4 + 16 + 2 + 10) \times 0.5) = 17$ 2. ${{1, 3}, {2, 4}}:\ $最优方案为 $\mathrm{max}(2 + 8 - 4 + 9, (4 + 16 + 10) \times 0.5) = 15$

可以证明，对于样例的最优分配方案答案即为 $ 15 $，且最优方案是唯一的。

约定与限制

输入数据已经给出。以下是对于所有输入数据，均满足的限制：

$2 \leq N, M \leq 5000, 0 \leq K \leq 5000, 0 \leq a_i \leq 10 ^ 4, 0 \leq b_i \leq 10 ^ 6;$

对于操作 $1$，有 $|w_i| \leq 10 ^ 4$，且此时 $w_i$ 为整数；

对于操作 $2$，有 $0.5 \leq w_i \leq 2$，且最多有一位小数；

对于一对 $(u_i, v_i)$ 最多只有一个限制；

对于任意分配方案，所有小队的麻烦程度均不小于 $1$。请注意，可能存在一些情况使得某些小队麻烦程度会非常大，可能会带来不必要的精度误差，请谨慎处理；

最优答案满足 $1 \leq \mathrm{ans} \leq 2 ^ {30}$。

评测方式

我们有十个评分文件 spring1.ans~spring10.ans，分别对应每个测试点作为评分标准；每个评分文件共 $11$ 行，第 $i$ 行一个评分参数 $w_i$，具体意义将在下面给出。

本题中，每个测试点单独进行评分，每个测试点 $10$ 分。

如果选手的输出格式不合法，则得 $0$ 分。

如果你的输出不满足以下条件，得 $0$ 分：

1. $\sum_{i=1}^N c_i = N$，且对于所有 $c_i$ 有 $0 \leq c_i \leq N$；
2. 所有 $N$ 个小动物均各自被分配到 $M$ 个小队中的一个，且仅被分配一次。

否则，我们认为你的方案正确，并按照以下规则得分。

对于每个测试点，我们设置了 $11$ 个评分参数 $w_0,w_1,w_2,…,w_9,w_{10}$，有 $w_i \lt w_{i + 1}$。

如果你的答案大于 $w_0$，那么你这个测试点得 $0$ 分；

如果你的答案不大于 $w_{10}$，那么你可以得到 $10$ 分；

否则，我们设你的答案为 $x$，设 $i$ 满足 $w_{i + 1} \leq x \lt w_i$，那么对于该测试点你可以得到 $i + 1 - \frac {\mathrm{out} - w_{i + 1}} {w_i - w_{i + 1}}$ 分，按四舍五入保留一位小数；也就是说，9.95 分及以上的提交均算作 10.0 分。

你该题的得分是所有测试点得分加和后四舍五入；也就是说，99.5 分以上的提交均算作 100 分。

下发文件

选手文件见题目描述上方附加文件

在附加文件里，有 spring1.out~spring10.out。

同时，我们提供了 spring0.in，spring0.out，spring0.ans，对应样例在附加文件中。

同时，我们提供了一个 checker，来对你的输出进行检验。你可以在命令行运行：./checker #，这样 checker 会读取当前目录下的spring#.in 和 spring#.out 来评测你的方案的价值；如果目录下同时有 spring#.ans，那么 checker 会同时给出你的得分。

请注意，checker 不会检查输入文件正确性；如果你想测试非下发测试点，请注意输入文件的正确性，并满足约定与限制，否则检验结果可能不准确。