Description

插队是不良的行为，不要学习。

开始有 $n$ 个人排队做核酸，突然有 $m$ 个人来插队，求最后 $n+m$ 个人的做核酸的顺序。

Input Format

第一行一个整数 $n$ 表示初始队伍中的人数。

第二行 $n$ 个字符串表示 $n$ 个人的名字。

第三行一个整数 $m$ 表示插队的人数。

接下来 $m$ 行表示 $m$ 个插队的人，可以表示为以下形式：

    $1.$ 0 x name $\text{name}$ 插到第 $x$ 个人后面。

    $2.$ 1 x name $\text{name}$ 插到第 $x$ 个人前面。

Output Format

一行 $n+m$ 个字符串表示最终的队伍。

4
Bob Alice Mike Dog
3
0 1 John
1 1 Cat
1 3 pig

Cat Bob John pig Alice Mike Dog

Hint

$1≤n,m≤10^5$，保证所以字符串长度之和不超过 $10^6$。

Source

数据结构-链表