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 i-th 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⁹.

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¹⁵.

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.