#P17953. Big Balls

Big Balls

Big Balls

题目描述

数轴上有 nn 个球,从左到右编号为 1,2,…,n1,2,\ldots,n。相邻球的初始距离相等。第 ii 个球的重量为 wiw_i,初始运动方向为 cic_i,其中 L 表示向左,R 表示向右。

所有球同时开始以相同的恒定速率运动。两个球碰撞时,它们合并为一个球:

  • 新球的重量为两个球重量之和。
  • 新球沿碰撞前较重的球的方向运动;如果两球重量相等,新球向右运动。
  • 新球的运动速率与其他球相同。

等待所有可能的碰撞结束后,分别计算向左运动的球的总重量与向右运动的球的总重量。

你需要独立回答 qq 个询问。每个询问给出 l,rl,r,表示只保留初始编号属于 [l,r][l,r] 的球,再从初始状态开始上述过程。询问之间互不影响。

输入格式

第一行一个整数 nn,1≤n≤1061\le n\le10^6。

接下来 nn 行,每行包含整数 wiw_i 和字符 cic_i,满足 1≤wi≤1091\le w_i\le10^9,cic_i 为 L 或 R。

下一行一个整数 qq,1≤q≤1061\le q\le10^6。

接下来 qq 行,每行包含两个整数 li,ril_i,r_i,满足 1≤li≤ri≤n1\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

输出

3 0
6 0
0 6
0 11
6 2