Description

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

给出一个链表，链表中各个节点的数据区域值按绝对值已经按降序排列，现请你对该链表进行特定处理：

（1）将链表中数据区域值为奇数的节点移到链表的前面，且按节点值升序排列。

（2）链表中数据区域值为偶数的节点维持初始时的先后次序（降序次序），保持不变。

Format

Input

第1行，链表节点数量n和头指针head。

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

给出一个单链表，链表中n个节点的数据区域值已经按降序排列。

Output

输出特定处理后链表中各个节点的数据信息。

Samples

5 2
17 3
16 4
35 1
2 -1
8 0

17 2
35 1
16 4
8 3
2 -1

Limitation

1s, 1024KiB for each test case.

说明：本题不能确保链表的表头节点数据区域值为偶数。