玩具谜题

题目描述

$n$ 个小人围成一圈，按顺时针编号为 $0$ 到 $n-1$。每个小人有朝向：0 表示朝圈内，1 表示朝圈外。开始位于 0 号小人处。

每条指令给出方向 $a$ 和步数 $s$：0 表示向左数，1 表示向右数。站在朝内和朝外的小人处时，左右对应的编号变化方向相反。若当前小人的朝向与指令方向相同，就逆时针移动 $s$ 个位置；否则顺时针移动 $s$ 个位置。

请依次执行全部指令，输出最后所在小人的名字。

输入格式

第一行两个整数 $n,m$。接下来 $n$ 行，每行给出朝向和名字。再接下来 $m$ 行，每行给出方向和步数。

输出格式

输出最后所在小人的名字。

数据范围

$2\le n,m\le10^5$；名字不含空格；$1\le s<n$。

样例输入 1

3 2
0 Alice
1 Bob
0 Carol
0 1
1 1

样例输出 1

Alice

样例说明 1

从Alice出发，第一条指令移动到Carol，第二条指令回到Alice。