乐编出题组收到了一条用户反馈,乐编OJ上的n道题中有一道题的测试数据与其他题目的测试数据数量不同(其余题目的测试数据数量都相同)导致最终比赛的得分不一致。但是由于乐编出题组经费紧张,他们现在只有一个程序员可以用,而且因为硬件原因,这个程序员每次只能从系统中随机抽取部分题目,然后由系统将这些题目均分为两部分,假如把这两部分命名为T_1,T_2,那么系统能够给出的结果只有<、>、=这三种结果,分别表示T_1的测试数据数量少于、多于、等于T_2测试数据的数量。
现在,为了找出这道不同的题目,该程序员将所有的n道题目从1 - n进行编号,然后分别两两比较,并且把每一次的比较记录都详尽的记录下来。这个可怜的程序员请你帮帮他,根据比较记录找出这个不同的题目。
输入数据有若干行;
第一行有两个整数n,k(2\leq n\leq 10^3,1\leq k\leq 100),分别代表金币的总数和比较的次数。
接下来的2k行记录称重的情况和结果,每两行记录一次称重:
- 第一行包含若干个整数,其中第一个数p_i(1\leq p_i\leq n/2)代表系统均分的两部分题目的数量,随后紧接着是第一部分数据中题目的编号,最后才是第二部分数据中题目的编号,两个数之间通过空格隔开。
- 第二行使用一个字符来记录比较的结果:
(1)< 表示第一部分题目的测试数据的数量少于第二部分的;
(2)> 表示第一部分题目的测试数据的数量多于第二部分的;
(3)= 表示第一部分题目的测试数据的数量等于第二部分的;
输出异常的题目的编号,如果根据记录无法确定异常的题目,则输出0;
5 3 2 1 2 3 4 < 1 1 4 = 1 2 5 =
3
输入样例解释:
5 3 (总共有5道题目,一共记录了3次比较记录)
2 1 2 3 4 (第一次比较总共选取了4道题,均分为2道,第一部分为第1、2道,第二部分为第3、4道)
< (第一次比较的结果为第一部分题目的测试数据的数量少于第二部分的)
1 1 4 (第二次比较共选取了2道题,均分为1道,第一部分为第1道,第二部分为第4道)
= (第二次比较的结果为第一部分题目的测试数据的数量等于第二部分的)
1 2 5 (第三次比较共选取了2道题,均分为1道,第一部分为第2道,第二部分为第5道)
= (第三次比较的结果为第一部分题目的测试数据的数量等于第二部分的)
数据规模已在题面中给出,在此处将不再重复。
时间限制 | 1 秒 |
内存限制 | 512 MB |