问题陈述
从AtCoder站出发的火车有两个目的地:高桥站和青木站。
您将获得以下信息: N 火车。 的 i第火车 (1\leq i\leq N) 由一对描述 (S _ i,T _ i) 一个字符串和一个正整数。 这意味着火车到站 S _ i 到达AtCoder站 T _ i 分钟后,哪里 S _ i 等于 Aoki or Takahashi.
您将乘坐最早到达 AtCoder 站的开往高桥站的火车。 您乘坐哪趟列车?
约束
- 1\leq N\leq2\times10 ^ 5
- S _ i 等于
AokiorTakahashi(1\leq i\leq N). - 1\leq T _ i\leq10 ^ 9\ (1\leq i\leq N)
- If i\neq j,那么 T _ i\neq T _ j\ (1\leq i,j\leq N).
- 存在 i 与 S _ i={}
Takahashi. - N 和 T _ i\ (1\leq i\leq N) 均为整数。
输入
输入由标准输入按以下格式给出:
N S _ 1 T _ 1 S _ 2 T _ 2 \vdots S _ N T _ N
输出
如果他正在服用 i第火车 (1\leq i\leq N),打印整数 i.
示例输入 1
5 Aoki 2 Takahashi 3 Takahashi 5 Aoki 10 Takahashi 15
示例输出 1
2
给出了到达AtCoder站的五趟列车的信息。 其中三个是前往高桥站的: 2- 火车三分钟后到达, 3-rd 火车五分钟后到达, 5第趟列车到达 15 分钟后。
的 2-nd 火车是其中最早到达的,所以 2 。
示例输入 2
8 Aoki 748 Aoki 436 Aoki 170 Aoki 587 Aoki 972 Aoki 331 Takahashi 532 Takahashi 523
示例输出 2
8
请注意,给定的到达时间可能无法排序。