填空题

配方制作-研发

Question

明明最近迷上了《明日之后》这款游戏。在这款游戏中有一个配方制造系统，玩家可以利用手中的资源和材料，来制造武器和道具。例如，玩家如果需要制造一个小木柜，需要3块木板，而制造一块木板，又需要120个木头和2个小树枝，并且需要走到建筑加工台前制作。而采集木头和小树枝又需要一定的时间。

玩了一段时间之后，明明开始好奇在游戏中做什么最花时间。虽然游戏中已经有标明每个物品的制造时间，但是明明更想通过自己的游戏经历来统计实际需要的时间。明明根据自己的操作，记录下了自己游戏中每个操作事件的开始和结束时间，按时间顺序汇总成了一张表，如下所示：

从上表可以看出，“制造1个小木柜”这个操作，总共用时2000-1=1999秒时间，其中包含两部分：制造3块木板的耗时（1000-5=995秒）和自身的耗时（1999-995=1004秒）。同样的，制造3块木板的995秒耗时中，也包括3部分：收集360个木头的耗时（20-10=10秒）、收集6个小树枝的耗时（40-25=15秒）以及自身耗时（995-10-15=970秒）。在这些操作当中，“制造1个小木柜”自身耗时1004秒，是所有操作中自身耗时最多的一个操作。

明明想知道自己做的这些操作中，哪个操作自身所花的时间是最多的。给出这张事件记录表，你可以帮明明计算一下吗？

数据范围：输入数据组数满足 ，每组数组中操作数满足 ，操作中的数都满足 、 时间结束和开始信息满足
进阶：空间复杂度 ，时间复杂度

输入描述：

输入中包含多组数据。输入的第一行是一个整数T(T<=100)，表示后续有多少组测试数据。

每组测试数据第一行是一个整数N(N<=100000)，表示记录的行数。随后是N行记录，每行包括3个整数t（030）、e(030)、s(0或1)，表示事件的时间、事件的id，以及开始或结束信息（0表示开始，1表示结束）。这些记录按照时间先后顺序给出，任意两行的时间均不相同。保证任意一个事件仅出现一次开始和一次结束，且开始时间在结束之前。保证子任务一定先于父任务结束。

输入样例： 1 8 1 1 0 5 2 0 10 3 0 20 3 1 25 4 0 40 4 1 1000 2 1 2000 1 1 输出描述：

对于每一组测试数据，输出一个整数，表示自身所花时间最多的事件id。如果有多个满足条件的事件，则输出事件id最小的那个。

输出样例 1