ONORIVER1  Ono at the river 1
Oňo the grasshopper wants to cross the river. But the river is very wide – w meters from one bank to the other, and Oňo can only jump up to d meters at once. Fortunately, there are n lily pads growing in the river. They’re not big enough yet, but once they are adult, they will be able to hold Oňo’s weight.
The ith lily pad is located m_{i} meters away from the left bank, where Oňo is right now. It will become able to support Oňo s_{i} seconds from now. But e_{i} seconds from now it will become too old and die.
Oňo is very fast and he can perform multiple jumps (each up to d meters) in a single second – every jump is practically instant. But he is still nervous. If he doesn’t plan things through, he could end up jumping across some lily pads only to find out there is no way forward, and now the lily pads behind him are gone and he can’t even get back! Oh, the horror! To prevent this, Oňo will only jump across the lily pads when he can immediately get from one side of the river to the other without stopping.
It would be great if someone wrote a program telling him at what time he can do so, and the total time that the river is crossable.
Task
Each lily pad has a time s_{i} when it turns adult and a time e_{i} when it dies; it can hold Oňo from the s_{i}th to the e_{i}th second. The lily pad is located m_{i} meters from the left bank of the river.
Find the earliest time that Oňo can cross the river without stopping, and also how many seconds there are such that he is able to do so.
Note that Oňo is not brave enough to jump from a lily pad which grows old at time t to a lily pad which becomes adult at the same time t  in other words, you may imagine that at the beginning of each second, first the appropriate lily pads die and then the appropriate lily pads become adult.
Input
The first line contains an integer 1 ≤ T ≤ 3  the number of test cases. The only input file with T > 1 is the sample shown below.
T test cases follow, each ends with a blank line.
The first line contains three integers n, w and d  the number of lily pads, the width of the river, and Oňo’s jump distance, where 1 ≤ n ≤ 500 000 and 1 ≤ d < w ≤ 10^{9}.
n lines will follow, each containing three integers m_{i} s_{i} e_{i} describing one lily pad: its distance in meters from the left bank, the time it turns adult, and the time it grows old. 0 < m_{i} < w and 1 ≤ s_{i} < e_{i} ≤ 10^{15}.
No two lily pads with the same position m_{i} will be alive at the same time, in particular if any two lily pads have the same m_{i}, one will die at least a second before the other becomes adult.
Output
For each test case, output two integers e and t in a single line, where e is the earliest time at which Oňo can jump all the way from the left to the right bank of the river without stopping, and t is the total number of seconds during which he can do so (not necessarily continuously from e).
If Oňo can never cross the river, print e as −1.
Examples
Input:
3
7 60 10
10 1 10
20 1 7
20 8 11
40 1 20
50 4 15
30 5 12
30 1 3
2 100 80
1 1 5
81 5 123
20 5 1
1 1 189
2 1 2
3 1 2
4 1 2
2 109 189
3 109 189
4 109 323
1 281 462
2 281 323
3 281 323
2 337 743
3 337 462
4 337 462
1 616 743
3 616 743
4 616 1016
1 874 1327
2 874 1327
3 874 1327
4 1163 1327
Output:
5 4
1 0
1 681
In the first case, at time 5, the first, second, fourth, fifth, and sixth lillies are alive, and Oňo can jump across. He can do so until the 7th second for a total of 2 seconds, when the second lily pad dies, then again from the 8th second to the 10th second, after which the first lily pad dies and the river becomes uncrossable forever.
In the second case the lily pads just barely miss themselves, and Oňo can never get across.
hide comments
ryloric:
20190818 14:47:51
Hi @Hodobox, is my last submission(24260099) anywhere close to the time limit? I'm wondering if Ocaml is not the right language with this TL or if my solution is just too slow.

Added by:  Hodobox 
Date:  20190526 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  own problem 