Problem A: Greedy Trading


Trading CDFs1 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 000Number of commands
−100 ≤ k ≤ 100Update values


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

Sample Input

u -5
u 0
u 2
u 1
u 3
u 1

Sample Output

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

Sample Explanation

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.

CDF – contract for difference.