这是网上的一段小短文，现在你成为了命运的管理员，掌握了两个人的人生轨迹。

每个人都有若干条命运记录，每条记录由一个日期和一个行为组成，例如：

2005-07-18 birth

表示这个人在 2005-07-18 这一天发生了 birth 这一命运事件。

接下来会进行若干次操作。每次操作中，一方会修改另一方的一条命运记录，同时自己也要付出代价：将自己时间最早出现的 happy 命运改为 unhappy。

你需要按照操作顺序依次执行所有修改，并输出两个人最终的命运列表。

输入描述

第一行输入三个整数 $a, b, m(1 \leq a, b, m \leq 10^3)$

分别表示：

• 第一个人的初始命运条数为 $a$
• 第二个人的初始命运条数为 $b$
• 操作次数为 $m$

接下来 $a$ 行，描述第一个人的初始命运。 每行两个字符串 date action，表示一条命运记录。

再接下来 $b$ 行，描述第二个人的初始命运。 每行两个字符串 date action，表示一条命运记录。

接下来共有 $3 * m$ 行，每 $3$ 行为一组，表示一次操作：

第 $1$ 行为一个整数 $op$：

• $op = 1$：表示第一个人修改第二个人的命运
• $op = 2$：表示第二个人修改第一个人的命运

第 $2$ 行输入两个字符串 old_date old_action，表示被修改者当前已有的一条命运记录

第 $3$ 行输入两个字符串 new_date new_action，表示这条命运记录被修改后的新内容

数据保证对于每次操作：

1. 被修改者的命运列表中，一定存在且仅存在一条记录恰好等于 old_date old_action。
2. 操作者的命运列表中，一定至少存在一条行为为 happy 的记录。
3. 日期字符串格式固定为 YYYY-MM-DD，且可以按字典序比较日期先后。
4. 命运字符串长度 $\leq 100$

操作规则

对于每次操作，按如下顺序执行：

1. 找到被修改者命运列表中那条等于 old_date old_action 的记录
2. 将其修改为 new_date new_action
3. 在操作者的命运列表中，找到日期最早的一条 happy 记录，将它的行为改为 unhappy

特别地：若有多条 happy 记录，取日期最早的一条。题目保证每次操作时，操作者一定存在至少一条 happy 记录，因此不会出现无法修改的情况

输出描述

输出两部分。

第一部分输出第一个人最终的命运，共 $a$ 行。 第二部分输出第二个人最终的命运，共 $b$ 行。

每行输出两个字符串：

date action

输出顺序与各自命运列表中的当前顺序一致。

说明：“修改一条命运”仅改变该条记录的内容，不改变它在命运列表中的位置。将 happy 改为 unhappy 时，同样只修改该记录的行为，不改变其位置

样例输入

3 2 2
2005-07-18 birth
2005-07-20 happy
2005-07-22 study
2005-07-19 happy
2005-07-21 travel
1
2005-07-21 travel
2005-07-21 ill
2
2005-07-22 study
2005-07-22 success

样例输出

2005-07-18 birth
2005-07-20 unhappy
2005-07-22 success
2005-07-19 unhappy
2005-07-21 ill