Problem Statement

A certain refrigerator assigns each drink a $6$-digit numeric string as its ID.

This refrigerator stores $N$ drinks. The $i$-th drink has ID $S_i$ and size $V_i$. $S_1, \dots, S_N$ are distinct.

Answer $Q$ queries. Each query is given in the form of $6$-digit numeric strings $x, y$, and asks the following.

• Among the drinks stored in this refrigerator, find the sum of the sizes of those whose assigned ID $s$ satisfies the following for every $k = 1, \dots, 6$.
• $x_k \leq s_k \leq y_k$, where $s_k, x_k, y_k$ denote the values represented by the $k$-th digits of $s, x, y$, respectively.

Constraints

• $N$ is an integer.
• $1 \leq N \leq 3 \times 10^5$
• $S_i$ is a string consisting of digits (0-9).
• $|S_i| = 6$
• $S_1, \dots, S_N$ are distinct.
• $V_i$ is an integer.
• $1 \leq V_i \leq 10^9$
• $Q$ is an integer.
• $1 \leq Q \leq 3 \times 10^5$
• In each query, $x$ and $y$ are strings consisting of digits (0-9).
• In each query, $|x| = |y| = 6$.

Input

The input is given from Standard Input in the following format:

N
S_1 V_1
\dots
S_N V_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Here, $\mathrm{query}_q$ is the $q$-th query, given in the following format:

x y

Output

Output $Q$ lines. The $q$-th line should contain the answer to the $q$-th query.