题目描述

小蓝是一名计算机专业的学生，最近他学习了《操作系统》、《数据结构》等课程，他设计了一种名为“冷热数据队列”的数据结构，来对数据页进行管理。

冷热数据队列 $q$ 可以看做由两个子队列组成：长度为 $n_1$ 的热数据队列 $q_1$ 和长度为 $n_2$ 的冷数据队列 $q_2$。当我们需要访问某个数据页 $p$ 时：

1. 若 $p$ 不在队列 $q$ 中（即既不在 $q_1$ 中，也不在 $q_2$ 中），则加载数据页 $p$ ，并插入到 $q_2$ 的首部。
2. 若 $p$ 已经在队列 $q$ 中，则将 $p$ 移动至 $q_1$ 首部。
3. 当 $q_1$ 或 $q_2$ 队列容量不足时，会将其尾部的数据页淘汰出去。
4. 当 $q_1$ 已满，但 $q_2$ 未满时，从 $q_1$ 中淘汰出的数据页会移动到 $q_2$ 首部。

输入格式

输入的第一行包含两个正整数 $n_1,n_2$，用一个空格分隔。

第二行包含一个整数 $m$ ，表示操作次数。

第三行包含 $m$ 个正整数 $v_1,v_2,··· ,v_m$ ，表示依次访问到的数据页的编号，相邻整数之间使用一个空格分隔。

输出格式

输出两行。

第一行包含若干个整数，相邻整数之间使用一个空格分隔，依次表示 $q_1$ 中的数据页。

第二行包含若干个整数，相邻整数之间使用一个空格分隔，依次表示 $q_2$ 中的数据页。

3 3
10
1 2 3 4 3 2 2 1 3 4

4 3 2
1

解释 #1

数据范围

• 对于 $20\%$ 的评测用例，$1≤n_1,n_2≤10$，$1≤m≤10$；
• 对于 $40\%$ 的评测用例，$1≤n_1,n_2≤20$，$1≤m≤100$；
• 对于 $60\%$ 的评测用例，$1≤n_1,n_2≤100$，$1≤m≤1000$；
• 对于 $80\%$ 的评测用例，$1≤n_1,n_2≤10^3$，$1≤m≤10^4$；
• 对于所有评测用例，$1≤n_1,n_2≤10^4$，$1≤m≤10^5$，$0≤v_i≤10^4$。

额外挑战

• 对于额外挑战的评测用例，$1≤m≤10^6$。