B. Big Balls
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. Nežmah likes playing with balls. He has placed $$$n$$$ balls on a line so that ball $$$i$$$ is the $$$i$$$-th leftmost ball. Every ball has its weight, which we denote with $$$w$$$, and the direction it will move to, either left or right.

Once he is happy with his setup, all of Mr. Nežmah's balls simultaneously start rolling in their chosen direction. All neighboring balls are equally distant from each other, and all balls move with equal constant speed.

When two balls of weights $$$w_i$$$ and $$$w_j$$$ collide, they merge into one big ball. Its weight is equal to the sum of the weights of the balls that collided, $$$w_i + w_j$$$, and its direction corresponds to the direction of the heavier of the two balls. If both balls have the same weight, the resulting ball will move to the right.

Mr. Nežmah noticed that, if enough time passes to let all collisions happen, the remaining balls can be split into two sets – balls that move left and balls that move right. For both of those sets, he wants to know the sum of the weights of the balls in it. Notice that the sum of the two numbers will correspond to the sum of the weights of the initial balls.

He believes this problem is too easy, so he wants you to solve it independently for $$$q$$$ different subarrays of balls. Specifically, in the $$$i$$$-th query, he gives you numbers $$$l_i$$$ and $$$r_i$$$, and he wants you to answer his problem if we only consider the balls denoted with $$$l_i, l_i+1, ..., r_i$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), the number of balls.

The next $$$n$$$ lines contain descriptions of the balls. In the $$$i$$$-th line, there is an integer $$$w_i$$$ ($$$1 \leq w_i \leq 10^9$$$), followed by a letter $$$c_i$$$, representing the $$$i$$$-th ball's weight and direction, respectively. $$$c_i$$$ will be L if the ball initially moves to the left, or R if it moves to the right.

The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$), the number of Mr. Nežmah's queries.

The next $$$q$$$ lines contain descriptions of the queries. In the $$$i$$$-th line there are integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$), the endpoints of the subarray.

Output

For each query, output two integers: the sum of weights of balls that will end up moving to the left, and the sum of weights of balls that will end up moving to the right.

Example
Input
5
3 R
1 R
2 L
3 L
2 R
5
2 3
2 4
1 3
1 5
2 5
Output
3 0
6 0
0 6
0 11
6 2