AT_abc465_f [ABC465F] Sjeltzer?

ある冷蔵庫では、ドリンクに $ 6 $ 桁の数字列を ID として割り振っています。 この冷蔵庫には $ N $ 個のドリンクが保管されています。 $ i $ 番目のドリンクの ID は $ S_i $ 、サイズは $ V_i $ です。 $ S_1, \dots, S_N $ は相異なります。 $ Q $ 個のクエリに答えてください。各クエリは $ 6 $ 桁の数字列 $ x, y $ の形式で与えられ、内容は以下の通りです。 - この冷蔵庫にあるドリンクのうち、割り振られた ID $ s $ がどの $ k = 1, \dots, 6 $ についても以下を満たすようなものについて、そのサイズの総和を求めよ。 - $ s, x, y $ の $ k $ 桁目の数字が表す値を $ s_k, x_k, y_k $ とおいたとき、 $ x_k \leq s_k \leq y_k $ を満たす。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ V_1 $ $ \dots $ $ S_N $ $ V_N $ $ Q $ $ \mathrm{query}_1 $ $ \vdots $ $ \mathrm{query}_Q $ ここで、 $ \mathrm{query}_q $ は $ q $ 個目のクエリであり、以下の形式で与えられる。 > $ x $ $ y $

$ Q $ 行出力せよ。 $ q $ 行目には $ q $ 個目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 個目のクエリにおいて、条件を満たすドリンクは $ 3,4 $ 番目のドリンクです。 $ 2 $ 個目のクエリにおいて、条件を満たすドリンクは存在しません。 $ 3 $ 個目のクエリにおいて、条件を満たすドリンクは $ 1,2,3,4,5 $ 番目のドリンクです。 $ 4 $ 個目のクエリにおいて、条件を満たすドリンクは存在しません。 ### Constraints - $ N $ は整数 - $ 1 \leq N \leq 3 \times 10^5 $ - $ S_i $ は数字 (`0`-`9`) からなる文字列 - $ |S_i| = 6 $ - $ S_1, \dots, S_N $ は相異なる - $ V_i $ は整数 - $ 1 \leq V_i \leq 10^9 $ - $ Q $ は整数 - $ 1 \leq Q \leq 3 \times 10^5 $ - 各クエリにおいて、 $ x, y $ は数字 (`0`-`9`) からなる文字列 - 各クエリにおいて、 $ |x| = |y| = 6 $