#P18230. The Grand Contest

The Grand Contest

The Grand Contest

Grand Contest 有很多道题,比赛持续时间也很长。队伍 1 和队伍 2 参加了这场比赛,两支队伍一共进行了 nn 次提交。每次提交的结果为正确或错误。某支队伍对一道题的提交得到正确结果后,就认为该队伍解出了这道题。

比赛结束后,首先按照解题数从多到少排名。解题数相同时,总用时较少的队伍排名靠前。总用时是每道已解出题目的用时之和。一道已解出题目的用时为:

  • 从比赛开始到该队伍对这道题的第一次正确提交所经过的分钟数;
  • 加上该队伍在这次正确提交之前,对这道题的每次错误提交带来的 pp 分钟罚时。

未解出的题目不计入总用时。如果解题数和总用时都相同,队伍 1 排在队伍 2 前面。

评委准备测试一个名为“移除时间区间”的功能:选择两个整数 L,RL,R,满足 0≤L<R0\le L<R,从比赛中移除时间区间 [L,R][L,R],并按以下规则修改所有提交时刻:

  • 原提交时刻小于 LL:不变;
  • 原提交时刻在 [L,R][L,R] 内:变为 LL;
  • 原提交时刻大于 RR:减少 R−LR-L。

这些操作只改变提交时刻,不改变各次提交的相对顺序,包括修改后时刻相同的提交。

请找出一个区间,使得移除它后,两支队伍的排名发生交换。要求首先最小化 R−LR-L;长度相同时,再最小化 LL。如果不存在这样的区间,输出无解。

输入格式

第一行包含一个整数 TT,表示测试用例数。

对于每个测试用例:

第一行包含两个整数 n,pn,p,表示提交总数和每次错误提交的罚时。

接下来 nn 行,按照原提交顺序描述各次提交。每行包含四个整数 a,b,c,da,b,c,d:

  • a∈{1,2}a\in\{1,2\},表示提交的队伍;
  • bb,表示提交的题目编号;
  • cc,表示从比赛开始到此次提交所经过的分钟数;
  • d∈{0,1}d\in\{0,1\}。d=1d=1 表示正确,d=0d=0 表示错误。

保证各次提交的原提交时刻非递减。

输出格式

对于每个测试用例,输出一行。

如果存在满足要求的区间,输出两个整数 L,RL,R,表示长度最短且在此基础上 LL 最小的区间;否则输出 −1-1。

样例

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

数据范围

对于所有数据:

  • 1≤T≤4×1051\le T\le4\times10^5;
  • 1≤n≤4×1051\le n\le4\times10^5;
  • 1≤p≤10121\le p\le10^{12};
  • a∈{1,2}a\in\{1,2\};
  • 1≤b≤1091\le b\le10^9;
  • 1≤c≤10121\le c\le10^{12};
  • d∈{0,1}d\in\{0,1\};
  • 所有测试用例的 nn 之和不超过 4×1054\times10^5。

一支队伍可能对已经解出的题目继续提交。计分时只使用第一次正确提交,以及它之前的错误提交。