L. The Grand Contest
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the Grand Contest, there are many problems and a very long duration. Team $$$1$$$ and team $$$2$$$ participated in this contest, which had a total of $$$n$$$ submissions. Each submission can either get a correct or incorrect verdict. A problem is considered solved by a team when the submission from that team is correct.

After the contest ends, teams are ranked by the most problems solved. Teams that solve the same number of problems are ranked by the least total time. The total time is the sum of the time consumed for each solved problem. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first correct submission, plus $$$p$$$ penalty minutes for each previously incorrect submission for that problem. There is no time consumed for a problem that is not solved. In case of a tie, team $$$1$$$ ranks before team $$$2$$$.

The judges of the Grand Contest will test a feature named "remove interval", which allows selecting two integers $$$L$$$ and $$$R$$$ ($$$0 \le L \lt R$$$) and remove the time interval $$$[L,R]$$$ in minutes from the contest such that:

  • All submissions with submission time less than $$$L$$$ minutes are unaffected;
  • All submissions with submission time in $$$[L,R]$$$ minutes have their submission time changed to $$$L$$$ minutes from the beginning;
  • All submissions with submission time more than $$$R$$$ minutes have their submission time reduced by $$$(R-L)$$$ minutes.

It is important to note that the above changes will only affect the submission times of certain submissions but will not affect the relative order of the submissions.

You need to find the shortest time interval $$$[L,R]$$$ in minutes such that after removing this interval from the contest, the rankings of the two teams will change, or indicate that such an interval does not exist. If there are multiple such intervals, you need to find the one with the smallest $$$L$$$.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 4 \times 10^5$$$), indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ ($$$1 \le n \le 4 \times 10^5$$$) and $$$p$$$ ($$$1 \le p \le 10^{12}$$$), indicating the number of submissions and the penalty minutes.

Then $$$n$$$ lines follow, describing the submissions during the contest in order. Each line contains four integers $$$a$$$ ($$$a \in \{1,2\}$$$), $$$b$$$ ($$$1 \le b \le 10^9$$$), $$$c$$$ ($$$1 \le c \le 10^{12}$$$), and $$$d$$$ ($$$d \in \{0,1\}$$$), indicating team $$$a$$$ submitted on problem $$$b$$$ at $$$c$$$ minutes from the beginning of the contest and got verdict $$$d$$$. If $$$d=1$$$, the submission is correct and solves the problem; otherwise, the submission is incorrect. It is guaranteed that the submission time is non-decreasing.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4 \times 10^5$$$.

Output

For each test case, output a line. If there exists a feasible time interval in minutes, output two integers $$$L$$$ and $$$R$$$, indicating the shortest interval with the smallest $$$L$$$. Otherwise, output $$$-1$$$.

Example
Input
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
Output
120 160
-1