Nežmah 先生喜欢玩球。他在一条直线上放置了 $n$ 个球，使得球 $i$ 是从左往右数第 $i$ 个球。每个球都有其重量（记为 $w$）和移动方向（向左或向右）。

一旦他对设置感到满意，Nežmah 先生的所有球就会同时开始向它们选择的方向滚动。所有相邻球之间的距离相等，且所有球都以相同的恒定速度移动。

当两个重量分别为 $w_i$ 和 $w_j$ 的球相撞时，它们会合并成一个大球。合并后球的重量等于相撞两球的重量之和 $w_i + w_j$，其移动方向与两球中较重者的方向一致。如果两球重量相同，则合并后的球将向右移动。

Nežmah 先生注意到，如果经过足够长的时间让所有碰撞都发生，剩下的球可以被分成两个集合——向左移动的球和向右移动的球。对于这两个集合，他想知道其中球的重量之和。请注意，这两个重量之和将等于初始球的重量总和。

他认为这个问题太简单了，所以他希望你对 $q$ 个不同的球的子区间独立求解。具体来说，在第 $i$ 次查询中，他会给出两个数 $l_i$ 和 $r_i$，并希望你回答如果只考虑编号为 $l_i, l_i + 1, \dots, r_i$ 的球时的答案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示球的数量。

接下来的 $n$ 行包含球的描述。在第 $i$ 行中，包含一个整数 $w_i$ ($1 \le w_i \le 10^9$)，后跟一个字母 $c_i$，分别表示第 $i$ 个球的重量和方向。如果球最初向左移动，则 $c_i$ 为 L；如果向右移动，则为 R。

下一行包含一个整数 $q$ ($1 \le q \le 10^6$)，表示 Nežmah 先生的查询次数。

接下来的 $q$ 行包含查询的描述。在第 $i$ 行中，包含整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)，表示子区间的端点。

输出格式

对于每个查询，输出两个整数：最终向左移动的球的重量之和，以及最终向右移动的球的重量之和。

样例

输入样例 1

5
3 R
1 R
2 L
3 L
2 R
5
2 3
2 4
1 3
1 5
2 5

输出样例 1

3 0
6 0
0 6
0 11
6 2