题目描述

给定一个单链表 L ，请编写程序输出 L 中间结点保存的数据。

• 如果链表有一个中间结点，输出该结点数据；
• 如果链表有两个中间结点，输出第二个中间结点的数据。

输入格式：

每个输入包含一个测试用例。

题目描述

给定一个单链表 $L$ ，请编写程序输出 $L$ 中间结点保存的数据。

如果有两个中间结点，则输出第二个中间结点保存的数据。例如：

给定 $L$ 为 $1→7→5$，则输出应该为 $7$ ；

给定 $L$ 为 $1→2→3→4$，则输出应该为 $3$ ；

输入描述

每个输入包含 $1$ 个测试用例。

每个测试用例：

第一行给出链表首结点的地址、结点总个数正整数 $N （≤ 10^5）$。

结点的地址是 $5$ 位非负整数，$NULL$ 地址用 $-1$ 表示。

接下来有 $N$ 行，每行格式为：

$Address Data Next$

其中 $Address$ 是结点地址，$Data$ 是该结点保存的整数数据$（0 ≤ Data ≤ 10^8）$，$Next$ 是下一结点的地址。

输出描述

对每个测试用例，在一行中输出 $L$ 中间结点保存的数据。

如果有两个中间结点，则输出第二个中间结点保存的数据。

备注

已确保输入的结点所构成的链表 $L$ 不会成环，但会存在部分输入结点不属于链表 $L$ 情况 。

样例1

输入

00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451

输出

6

样例2

输入

10000 3
76892 7 12309
12309 5 -1
10000 1 76892

输出

7