Description

输入一个含n（n>=1）个节点单链表的相关信息。

将该单链表进行折半并翻转，依次输出折半翻转后的单链表节点信息。 将链表的后半部分节点个数为n//2个，将后半部分拼接在链表的前面，实现链表的折半与翻转操作。

Format

Input

第1行，输入单链表节点数量n（n>=1）和头指针head。

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

Output

输出折半并翻转后的单链表中各节点信息。

Samples

5 2
40 3
20 4
10 1
50 -1
30 0

40 3
50 2
10 1
20 4
30 -1

Limitation

1s, 1024KiB for each test case.

提示：可采用slow,fast双指针来寻找单链表的中间位置点，先找到链表中间位置，再进行链表翻转操作。