UOFTCC - A Subtle Surf

Alice has received an invitation from Bob to watch some TV on $D$ ($1 \leq D \leq 100$) days! Though spending time with him is nice, she's more concerned about exactly what channels they'll be watching. After all, being a guy, Bob is sure to be interested in viewing less sophisticated programs than she is.

On each day, a different set of $N$ ($1 \leq N \leq 100,000$) channels are available, numbered $1..N$. Each channel $i$ has a girliness value of $G_i$ ($0 \leq G_i \leq 10^9$) associated with it, indicating how much Alice would like to watch it. When she arrives at Bob's house, the TV is set to channel 1, but she'd like to surf to a channel with maximal girliness, and as quickly as possible.

Alice wants to be subtle about her channel surfing, however. She believes that Bob may notice if they stay on any channel for less than $T$ ($1 \leq T \leq 1000$) seconds before switching, or if the girliness value of the new channel is more than $C$ ($1 \leq C \leq 10^9$) greater than that of the current one. She needs a plan of action to maximize the girliness of the channel they end up watching, while minimizing the amount of time it'll take her to surf to such a channel.

Input

Line 1: 1 integer, $D$

For each day:

Line 1: 3 integers, $N$, $C$, and $T$

Line 2: $N$ integers, $G_{1..N}$

Output

For each day:

2 integers, the maximum channel girliness which Alice can surf to, and the minimum number of seconds required to arrive at a channel with this girliness, respectively

Example

Input:
2
6 3 5
3 4 0 8 12 6
4 1 2
5 7 7 5

Output:
8 10
5 0

Explanation of Sample

On the first day, Alice should switch to channel 6 after 5 seconds, and to channel 4 after another 5 seconds.

On the second day, Alice can't surf to either channel 2 or 3, so she should stay on channel 1.


Added by:SourSpinach
Date:2014-02-18
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem, used in the 2013 UofT ACM Tryouts

hide comments
2021-09-17 17:38:31
Please fix those "$" and "\leq" which make descriprion less readable.
2017-06-13 10:32:29
Can any one explain the test cases
2014-02-28 02:32:15 LeppyR64
Nice problem once I determined what the definition of "surfing" was. After that was fixing an overflowing sentinel value.
2014-02-20 18:08:27 Kevin Sebastian
tricky test cases??

RE: Nope.

Last edit: 2014-02-20 19:44:34
2014-02-18 10:47:52 Flago
Easy one ! :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.