题目描述

塔子哥和他的朋友们聚会，聚会中大家一起玩起了真心话大冒险的游戏。

游戏的规则是这样的：每个人会获得一张卡片，卡片会写着“真心话”或者“大冒险”。如果卡片上是真心话，就必须回答一个由主持人提出的关于自己的敏感问题。如果卡片上是大冒险，就必须执行一个由主持人安排的惊险或者刺激的任务。如果拒绝回答或者执行，就必须接受惩罚。

塔子哥他们使用的卡牌还有指定顺序的功能，每张卡片都有一个卡片编号，和下一张卡片编号，以及一个卡牌点数，塔子哥他们决定按卡牌指定的顺序来玩游戏。

塔子哥和朋友们还制定了一个规则，就是拿到中间卡牌的那个人可以根据点数获得奖励。当卡牌总数是偶数，就选择中间右边的那张作为中间卡牌。

现在塔子哥想快速地知道自己有没有轮空，需要你想办法写一个程序来解决这个问题。

注意，卡牌是顺序的，因此不可能出现环，但是有可能会有洗错的牌混进去，因此可能会存在不在这个队列里的牌。

输入描述

第一行输入两个数 $x$ ,$n$ ,表示真心话大冒险的第一张卡片编号（一段长度不超过50的字符串），和卡片总数 $n(1 \leq n \leq 10000)$。

后面输入 $n$ 行，每行表示一个节点 $i$ ，格式为：卡牌编号 卡牌点数 下一张卡牌编号(-1表示后面没有卡牌了)。

输出描述

输出一行 $ans$ ,表示中间卡牌的点数。

样例1

样例输入

00010 4
00010 2 41919
41919 4 11451
11451 3 00000
00000 1 -1

样例输出

3

样例2

样例输入

12345 3
56789 3 12300
12300 2 -1
12345 1 56789

样例输出

3