CDFs^{1} are instruments to
speculate on financial markets. A CDF is a contract stipulating that a seller
will pay to the buyer the difference between the current value of an asset
and its value at contract time. CDFs are traded between individual traders
and CDF providers. A CDF is started by making an opening trade on a
particular instrument with the CDF provider. This creates a ‘position’
in that instrument, which can be either long (taking advantage of prices
moving up) or short (taking advantage of prices moving down). There is
no expiry date. Once the position is closed, the difference between the
opening trade and the closing trade is paid as profit or loss.

Assuming that near real time access to stock quotes variation is available, your job is to help greedy traders by finding the sequences that maximize the value and their median. You should be able to do it also in near real time.

You should not be concerned that such information might not help traders at all. Let them play!

Develop a tool that receives updates on price variation for a given CDF instrument and that is able to answer queries on the sequences with maximum sum and their median value. Your tool should be as fast as possible!

A sequence of N lines starting either by u, q or x. Lines starting with u denote updates, where character u is followed by a single space and an integer number k. A line starting with q denotes a query command and a line starting with x should terminate the tool. All inputs start with an update command.

1 ≤ N ≤ 1 000 | Number of commands |

−100 ≤ k ≤ 100 | Update values |

Only command q produces output. The output is a single line with three integer numbers:

- Two integers denoting the starting position and the end position of the non-empty contiguous subsequence with the maximum sum with respect to the sequence of numbers received until now. Assume that updates are numbered from position 0 (see the sample output below). Notice that if there are two or more such subsequences, then you should output information concerning the last subsequence. By last subsequence we mean the one that ends at a later position and, if more than one subsequence ends at the same position, then we want the one that starts at a later position.
- The third integer denotes the median of that subsequence. Notice that in case the sequence length is even you should output the greatest of the middle two values.

u -5 q u 0 q u 2 u 1 u 3 q u 1 q x

0 0 -5 1 1 0 2 4 2 2 5 2

We observed a sequence of updates for a given CDF instrument. Its value decreased by 5, but then it increased by 2, 1, 3 and 1. So, at the end, its value has increased by 2, but we are not interested on that. We want to answer queries q on non-empty subsequences with the maximum sum with respect to the sequence of updates till the query time. For the first query, we have that the subsequence with the maximum sum is −5 and its median is also −5, hence the output is 0 0 -5 where 0 is the index of the update instruction for value −5. For the second query we have the subsequence 0, hence the output is 1 1 0. For the third query, we have that the subsequence with the maximum sum is 2,1,3 and its median is 2, hence the output is 2 4 2 where 2 and 4 are the indexes of update instructions for values 2 and 3, respectively. For the last query, the subsequence with the maximum sum is 2,1,3,1 and its median is still 2, hence the output is 2 5 2.

- 1
- CDF – contract for difference.