No.43 文字列をやたらめったら繰り返す

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

olphe君は大手前プロコンに参加するにあたって文字列をお土産にしようと考えました。

お土産にする文字列は以下のようにして作成します。

①最初文字列は空である。

②クエリの数$N$が与えられる。

③今ある文字列の最後尾に文字列$s_i$を付け足す。

④今ある文字列の最後尾に同じものを$v_i$個付け足す。

(③、④は$N$回繰り返す。)

olphe君は無事に文字列を完成させましたが、前日に誤って文字列の一部を破壊してしまいました。

olphe君は急いで文字列を作り直そうとしましたが、各文字が何個必要なのかわかりません。

壊してしまった文字列の範囲(L文字目～R文字目という形式)があたえられるので、彼に代わって必要とする各文字の数を求めて下さい。

制約

• $1 ≦ N ≦ 1000$
• $1 ≦ L<=R ≦ 10^{18}$
• $1 ≦ |s_i| ≦ 1000$
• $0 ≦ v_i ≦ 1000$

olphe君が作った文字列の長さは$10^{18}$を越えない。

s_iは英小文字のみで構成される。

入力形式

入力は以下の形式で標準入力から与えられる。

N L R
s_1 v_1
s_2 v_2
......
s_N v_N

出力

各文字について必要とする数を出力して下さい。

入出力例

1 1 6
abcabc 0

2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

作りたい文字列はabcabcで、全部壊してしまったのでa,b,cが2個ずつです。

3 7 24
a 0
b 3
ac 3

9 7 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

作りたい文字列はababababacababababacababababacababababacです。