問題文

ABC 大学には N 人の一年生が在籍しています。クラスは 2 つあり、学籍番号 i 番の生徒のクラスは C_i 組です。今日は期末試験が返却され、学籍番号 i 番の生徒の点数は P_i 点でした。

以下の形式の質問が Q 個与えられます。j = 1, 2, \dots, Q それぞれについて答えてください。

• 学籍番号 L_j \sim R_j 番の 1 組生徒における、期末試験点数の合計
• 学籍番号 L_j \sim R_j 番の 2 組生徒における、期末試験点数の合計
• これら 2 つの値をそれぞれ求めよ。

制約

• 1 \leq N \leq 100000
• 1 \leq C_i \leq 2
• 0 \leq P_i \leq 100
• 1 \leq Q \leq 100000
• 1 \leq L_j \leq R_j \leq N
• 入力は全て整数

入力例 1

7
1 72
2 78
2 94
1 23
2 89
1 40
1 75
1
2 6

出力例 1

63 261

学籍番号 2 \sim 6 番の 1 組生徒における、期末試験合計点は 23+40=63 です。
また、学籍番号 2 \sim 6 番の 2 組生徒における、期末試験合計点は 78+94+89=261 です。

入力例 2

7
1 72
2 78
2 94
1 23
2 89
1 40
1 75
10
1 3
2 4
3 5
4 6
5 7
1 5
2 6
3 7
1 6
2 7

出力例 2

72 172
23 172
23 183
63 89
115 89
95 261
63 261
138 183
135 261
138 261

入力例 3

1
1 100
3
1 1
1 1
1 1

出力例 3

100 0
100 0
100 0

一方の組の生徒が存在しないケースもあります。

入力例 4

20
2 90
1 67
2 9
2 17
2 85
2 43
2 11
1 32
2 16
1 19
2 65
1 14
1 51
2 94
1 4
1 55
2 90
1 89
1 35
2 81
20
3 17
5 5
11 11
8 10
3 13
2 6
3 7
3 5
12 18
4 8
3 16
6 8
3 20
1 12
1 6
5 16
3 10
17 19
4 4
7 15

出力例 4

175 430
0 85
0 65
51 16
116 246
67 154
0 165
0 111
213 184
32 156
175 340
32 54
299 511
132 336
67 244
175 314
51 181
124 90
0 17
120 186