Description

链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表中的每个节点一般由数据区域和指针区域两部分构成，其中数据区域用于保存实际需要处理的数据元素，指针区域用来保存该节点相邻节点的存储地址。

已知列表data中存储了两个升序链表，现要将这两个链表按升序进行合并。输出升序排序后链表中各个节点的数据信息。

Format

Input

第1行，n个数据和两个链表的头指针heada、headb。

第2~n+1行，每行为两个数x和y。x表示节点数据区域的值，y表示节点指针区域的值。

Output

对两个链表按升序处理，输出合并后链表中各个节点的数据信息。

Samples

12 5 9
9 11
15 8
4 7
2 6
25 -1
3 2
8 10
6 0
23 -1
1 3
17 4
13 1

1 3
2 5
3 2
4 7
6 6
8 0
9 11
13 1
15 10
17 8
23 4
25 -1

Limitation

1s, 1024KiB for each test case.