J. Popping balloons
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In preparation for the party, you have been filling water balloons with such enthusiasm that you have not realized that almost none of them have the same amount of water. Instead of starting from scratch, you've decided to continue with your frenetic method, filling the balloons with an arbitrary amount of water, then discarding (and popping) those that are too big or too small.

For example, if you have inflated balloons with quantities of 16, 10, 9, 12 and 11 units of water, and you decide to discard the largest balloon and the two smallest ones, you will discard the balloons with quantities 9, 10 and 16, which will make you waste 35 units of water.

Input

There will be several test cases, represented by a number $$$C$$$ in the first line. Each test case contains the values $$$E$$$, $$$A$$$, and $$$B$$$. The number $$$E$$$ of events that will take place, and the values $$$A$$$ and $$$B$$$, representing the number of smallest and largest balloons to pop, respectively ($$$0\leq A+B \lt E$$$). $$$E$$$ lines appear below, each describing an event in chronological order with two possible formats:

  • H $$$x$$$: Indicating that a new balloon is inflated with an amount $$$x$$$ of water.
  • Q: Indicating that you are asking yourself the question of how much water would be wasted if you decided to stop inflating balloons at that moment. Remember that you are only asking yourself the question, you are not getting to pop any balloon.

All test cases start with at least $$$A+B$$$ events of type H, and contain at least one event of type Q.

  • $$$1 \leq C \leq 10.000$$$
  • $$$1\leq x\leq 10^{18}$$$
  • $$$A+B+1\leq E$$$
  • The total number of events, $$$E$$$, is less than or equal to $$$2 \cdot 10^{5}$$$
Output

For each event of type Q, write on a separate line the sum of the water that would be spent if the balloons were popped at that moment. As the sum can be very large, the result will be written modulo 1,000,000,009.

At the end of each test case write three dashes '—'.

Example
Input
2
8 1 1
H 1
H 2
H 3
P
H 4
P
H 5
P
8 2 3
H 1
H 1
H 1
H 1
H 2
P
H 100
P
Output
4
5
6
---
6
105
---