#P18230. The Grand Contest
The Grand Contest
The Grand Contest
Grand Contest 有很多道题,比赛持续时间也很长。队伍 1 和队伍 2 参加了这场比赛,两支队伍一共进行了 次提交。每次提交的结果为正确或错误。某支队伍对一道题的提交得到正确结果后,就认为该队伍解出了这道题。
比赛结束后,首先按照解题数从多到少排名。解题数相同时,总用时较少的队伍排名靠前。总用时是每道已解出题目的用时之和。一道已解出题目的用时为:
- 从比赛开始到该队伍对这道题的第一次正确提交所经过的分钟数;
- 加上该队伍在这次正确提交之前,对这道题的每次错误提交带来的 分钟罚时。
未解出的题目不计入总用时。如果解题数和总用时都相同,队伍 1 排在队伍 2 前面。
评委准备测试一个名为“移除时间区间”的功能:选择两个整数 ,满足 ,从比赛中移除时间区间 ,并按以下规则修改所有提交时刻:
- 原提交时刻小于 :不变;
- 原提交时刻在 内:变为 ;
- 原提交时刻大于 :减少 。
这些操作只改变提交时刻,不改变各次提交的相对顺序,包括修改后时刻相同的提交。
请找出一个区间,使得移除它后,两支队伍的排名发生交换。要求首先最小化 ;长度相同时,再最小化 。如果不存在这样的区间,输出无解。
输入格式
第一行包含一个整数 ,表示测试用例数。
对于每个测试用例:
第一行包含两个整数 ,表示提交总数和每次错误提交的罚时。
接下来 行,按照原提交顺序描述各次提交。每行包含四个整数 :
- ,表示提交的队伍;
- ,表示提交的题目编号;
- ,表示从比赛开始到此次提交所经过的分钟数;
- 。 表示正确, 表示错误。
保证各次提交的原提交时刻非递减。
输出格式
对于每个测试用例,输出一行。
如果存在满足要求的区间,输出两个整数 ,表示长度最短且在此基础上 最小的区间;否则输出 。
样例
2
6 20
1 1 60 0
2 2 60 0
2 2 120 1
1 2 180 1
1 2 180 0
2 2 300 1
2 20
1 1 300 1
2 2 300 1
120 160
-1
数据范围
对于所有数据:
- ;
- ;
- ;
- ;
- ;
- ;
- ;
- 所有测试用例的 之和不超过 。
一支队伍可能对已经解出的题目继续提交。计分时只使用第一次正确提交,以及它之前的错误提交。