Three friends Snow Gnome, Small Boy and Xephy were having fun in the biggest park in Lalalandia, when suddenly they saw the shooting range with prizes! As always, Small Boy asked for the biggest prize, and Snow Gnome said he would get it.

The shooting range consists of N towers each denoted by \(K_i\) lines (\(1 \le i \le N\)). Towers are described by blocks from the bottom to the top. Each block consists of \(A_{ij}\) cubes and the shooter gets \(B_{ij}\) coins for taking one cube in this block for \(1 \le j \le K_i\) (see the picture for more explanation).

The shooter gets Q shots. He shoots the bullets in straight line on height \(C_l\). After the bullet shoots the cube, it gets destroyed, and all cubes above it move down. Note that bullet, even after penetrating one tower, continues to go through and never goes down.

Xephy now wants to know how many points for each shot Snow Gnome got. Can you help him with that?

Input format

First line contains single integer N - the number of towers.

Next N lines describe the tower i (\(1 \le i \le N\)) - each contains single integer \(K_i\). Next \(K_i\) lines contain the numbers \(A_{ij}\) and \(B_{ij}\) for \(1 \le j \le K_i\) - the number of cubes and the coins for shooting one cube from this block, respectively.

Next line contains Q - the number of Snow Gnome's shots. The Q lines describe the lth shot (\(1 \le l \le Q\)) - each containing one integer \(C_l\) - the height of the lth shot.

Output format

The output should contain Q lines. lth line should contain single integer - points for Snow Gnome's lth shot (\(1 \le l \le Q\)).

Constraints:

\(1 \le N \le 10^5\)

\(1 \le K_i \le 10\)

\(1 \le A_{ij} \le 10^8\)

\(1 \le B_{ij} \le 10^9\)

\(1 \le Q \le 10^5\)

\(1 \le C _l \le 10^9\)