CTOI10D1  MP3 Player
Georg's new MP3 player has many interesting features, one of them being the key lock. All the keys are locked after more than T seconds of inactivity. After the key lock is engaged, no key performs its original function, but if any key is pressed, the key lock is disengaged.
For example, assume that T = 5 and the player is currently locked. Georg presses the key A, waits for 3 seconds, presses the key B, waits for 5 seconds, presses C, waits for 6 seconds, and presses D. In this case only the keys B and C perform their regular functions. Note that the keys became locked between C and D was pressed.
Sound level of the MP3 player is controlled by the + and  keys, increasing and decreasing volume by 1 unit respectively. The sound level is an integer between 0 and V_{max}. Pressing the + key at volume V_{max} or pressing the  key at volume 0 leaves the volume unchanged.
Task specification
Georg does not know the value of T. He wanted to find it by an experiment. Starting with a locked keyboard, he pressed a sequence of N + and  keys. At the end of the experiment Georg read the final volume from the player's display. Unfortunately, he forgot to note the volume before his first keypress. For the purpose of this task, the unknown initial volume will be denoted V_{1} and the known final volume will be denoted V_{2}.
You are given the value V_{2} and a list of keystrokes in the order in which Georg made them. For each key, you are given the type of the key (+ or ) and the number of seconds from the beginning of the experiment to the moment when the key was pressed. The task is to find the largest possible integer value of T which is consistent with the outcome of the experiment.
Input
The first line of the input contains three spaceseparated integers N, V_{max} and V_{2} (0 ≤ V_{2} ≤ V_{max}). Each of the next N lines contains a description of one key in the sequence: a character + or , a space and an integer C_{i} (0 ≤ C_{i}≤ 2 x 10^{9}), the number of seconds from the beginning of the experiment. You may assume that the keypresses are in sorted order and that all times are distinct (i.e., C_{i} < C_{i + 1} for all 1 ≤ i < N).
Output
If T can be arbitrarily large, output a single line containing the word "infinity" (quotes for clarity).
Otherwise, output a single line containing two integers T and V_{1} separated by a single space.
The values must be such that carrying out the experiment with locking time T starting at volume V_{1} gives the final volume V_{2}. If there are multiple possible answers, output the one with the largest T; if there are still multiple possible answers, output the one with the largest V_{1}.
(Note that at least one solution always exists: for T = 0 none of the keys performs its action, so it suffices to take V_{1} = V_{2}.)
Constraints
You may assume that 2 ≤ N ≤ 100000 and 2 ≤ V_{max} ≤ 5000.
In test cases worth 40 points N ≤ 4000.
In test cases worth 70 points N x V_{max} ≤ 400000.
Examples
Input:
6 4 3
 0
+ 8
+ 9
+ 13
 19
 24
Output:
5 4
For T = 5 the keys perform the following actions: unlock, unlock, +, +, unlock, .
For any V_{1} ∈; {2, 3, 4} we would get V_{2} = 3. Note that the output contains the largest possible V_{1}.
For T ≥ 6 the last two keystrokes will both be active, hence it will be impossible to have V_{2} = 3.
Input:
3 10 10
+ 1
+ 2
+ 47
Output:
infinity
If V_{1} = 10 then for any T we'll have V_{2} = 10.
hide comments
Phan Công Minh:
20100719 03:09:13
This is an error when i uploaded tests. sorry . I've fixed the error.


Balrog:
20100719 02:54:44
i have solevd all the testdata download from CEOI web,but get WA on SPOJ,is there seomthing wrong with testdata ,or add some new testdata?

Added by:  Phan Công Minh 
Date:  20100717 
Time limit:  0.105s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  CEOI 2010 