Thor's Journey

Thor learned which planet holds an Infinity Stone. All planets are connected as a perfect binary tree, and each planet has an energy value $E$.

A perfect binary tree numbers its root $1$, gives every other vertex $v$ the parent $(v/2)$, and holds $(2^N)-1$ vertices when its height is $N$. The figure above shows a perfect binary tree of height $3$. Planets $A$ and $B$ are connected when travel is possible from $A$ to $B$ and from $B$ to $A$. The path sum from planet $A$ to planet $B$ is the sum of energies of all planets on the path from $A$ to $B$. For instance, the path sum from $A$ to $A$ equals the energy of planet $A$.

The path sum from the planet where Thor stands to the planet with the Infinity Stone is $D$. Several planets can have path sum $D$ from the current position. Find how many planets can hold the Infinity Stone.

The first line gives $N$ ($1 \le N \le 17$). The second line gives the energy $E_i$ ($-1{,}000{,}000{,}000 \le E_i \le 1{,}000{,}000{,}000$) of each planet, $(2^N)-1$ numbers in total. The third line gives $Q$ ($1 \le Q \le 100{,}000$). Each of the next $Q$ lines gives the number $A$ ($1 \le A \le 2^N-1$) of the planet where Thor stands and a path sum $D$ ($-1{,}000{,}000{,}000 \le D \le 1{,}000{,}000{,}000$).

Print $Q$ lines. Each line prints the number of planets whose path sum from the planet where Thor stands equals $D$.

In the second query, the planets whose path sum from position $4$ equals $5$ are planet $5$ ($E[4] + E[2] + E[5] = 5$) and planet $3$ ($E[4] + E[2] + E[1] + E[3] = 5$), so the answer is $2$.