In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

Georg's new MP3 player has many interesting features, one of them being the key lock. All the keys are locked after more than 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 and the player is currently locked. Georg presses the key , waits for 3 seconds, presses the key , waits for 5 seconds, presses , waits for 6 seconds, and presses . In this case only the keys and perform their regular functions. Note that the keys became locked between and was pressed.

Sound level of the MP3 player is controlled by the `+`
and `-` keys, increasing and decreasing volume by unit respectively.
The sound level is an integer between and . Pressing the `+` key
at volume or pressing the `-` key
at volume leaves the volume unchanged.

Georg does not know the value of . He wanted to find it by an experiment.
Starting with a locked keyboard, he pressed a sequence of `+` 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
and the known final volume will be denoted .

You are given the value 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 which is
consistent with the outcome of the experiment.

The first line of the input contains three space-separated integers , and
(). Each of the next lines contains a description
of one key in the sequence: a
character '`+`' or '`-`', a space and an integer (), 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., for all ).

You may assume that and .

In test cases worth 40 points .

In test cases worth 70 points .

If can be arbitrarily large, output a single line containing the word "`infinity`"
(quotes for clarity).

Otherwise, output a single line containing two integers and separated by a single space.

The values must be such that carrying out the experiment with locking time starting at volume gives the final volume . If there are multiple possible answers, output the one with the largest ; if there are still multiple possible answers, output the one with the largest .

(Note that at least one solution always exists: for none of the keys performs its action, so it suffices to take .)

For the input data:

6 4 3 - 0 + 8 + 9 + 13 - 19 - 24

the correct result is:

5 4

For the keys perform the following actions: unlock, unlock, `+`, `+`, unlock, `-`.

For any we would get . Note that the output contains the largest possible .

For the last two keystrokes will both be active, hence it will be impossible to have .

For the input data:

3 10 10 + 1 + 2 + 47

the correct result is:

infinity

If then for any we'll have .

*Task author: Peter Fulla.*