芙莉莲的债务与魔法档案

• 时间限制：1 秒
• 内存限制：256 MB
• 输入：标准输入
• 输出：标准输出

题目描述

在击败魔王后的数年间，人类变化很快——他们寿命短暂，对档案混乱的耐心更短。芙莉莲当然不在乎……直到她开始在乎。

在第二次旅途中，她越来越频繁地面对自己诺言的后果。几十个公会仍然保存着她关于咒语、神器及魔法研究的旧记录。为了偿还其中一笔债务，芙莉莲必须将两个独立的咒语目录合并成一个官方卷轴。

档案中有两部编年史：

• 编年史 $A$——芙莉莲自己的记录，用长度为 $n$ 的数组 $a$ 表示；
• 编年史 $B$——魔法公会的记录，用长度为 $m$ 的数组 $b$ 表示。

每条记录是一个非负整数，表示咒语的魔法索引。需要组成一个长度为 $n+m$ 的数组 $c$，它是数组 $a$ 和 $b$ 的“交织”，即包含 $a$ 和 $b$ 的每个元素，且严格保持它们在 $a$ 和 $b$ 中的出现顺序。

更形式化地说，需要选择 $1 \le i_1 < i_2 < \dots < i_n \le n+m$，然后令 $c_{i_j} = a_j$，并将数组 $c$ 的剩余索引依次用数组 $b$ 的元素填充。

定义数组 $c$ 的最优性如下：

1. 考虑数组 $c$ 的所有前缀：先是仅有第一个元素，然后是前两个元素，然后是前三个，以此类推直到整个数组。
2. 对于每个这样的前缀，计算其 $\mathrm{mex}$——该前缀中未出现的最小非负整数。
3. 数组 $c$ 的最优性就是所有前缀的 $\mathrm{mex}$ 值之和。

要求选择数组 $a$ 和 $b$ 的“交织”方式，使得最终数组 $c$ 的最优性最大。

输入格式

第一行包含三个整数 $n, m, t$ ——数组 $a$ 和 $b$ 的长度，以及影响输出格式的参数 $t$（$1 \le n, m \le 8 \cdot 10^3$；$t \in \{1, 2\}$）。

第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^6$）。

第三行包含 $m$ 个非负整数 $b_1, b_2, \dots, b_m$（$0 \le b_i \le 10^6$）。

输出格式

若 $t = 1$，输出一个整数——数组 $c$ 可能的最大最优性。

若 $t = 2$，第一行输出最大最优性，第二行输出任意一个满足条件的数组 $c$，使其达到该最优性。

评分系统

只有通过了某组及其必要组的所有测试，才能获得该组的分数。

样例

样例 1

输入：

2 2 1
0 1
0 2

输出：

8

样例 2

输入：

4 4 2
1 0 3 1
2 0 4 3

输出：

28
1 0 2 3 0 4 3 1

样例 3

输入：

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

输出：

57