토르의 여행

토르는 인피니티 스톤이 있는 행성에 대한 정보를 얻었다. 모든 행성은 포화 완전이진트리 형태로 연결되어 있으며 각 행성은 에너지값 $E$를 가진다.

포화 완전이진트리는 루트 정점의 번호를 $1$로 하고 $1$번 정점을 제외한 모든 정점 $v$가 $(v/2)$번 정점을 부모로 가지며 높이가 $N$일 때 $(2^N)-1$개의 정점을 가지는 트리이다. 위 그림은 높이가 $3$인 포화 완전이진트리이다. 행성 $A$와 $B$가 연결되었다는 것은 $A$에서 $B$로, $B$에서 $A$로 이동할 수 있다는 뜻이다. 행성 $A$에서 $B$까지의 경로의 합은 $A$에서 $B$까지의 경로 위에 있는 모든 행성의 에너지 합이다. $A$에서 $A$까지의 경로의 합은 $A$ 행성의 에너지와 같다.

토르가 있는 행성에서 인피니티 스톤이 있는 행성까지의 경로의 합은 $D$이다. 현재 위치에서 경로의 합이 $D$인 행성은 여러 개일 수 있다. 인피니티 스톤이 있을 수 있는 행성의 개수를 구하라.

첫째 줄에 $N$($1 \le N \le 17$)이 주어진다. 둘째 줄에 각 행성의 에너지 $E_i$($-1{,}000{,}000{,}000 \le E_i \le 1{,}000{,}000{,}000$)가 $(2^N)-1$개 주어진다. 셋째 줄에 $Q$($1 \le Q \le 100{,}000$)가 주어진다. 다음 $Q$개의 줄에는 토르가 있는 행성의 번호 $A$($1 \le A \le 2^N-1$)와 경로의 합 $D$($-1{,}000{,}000{,}000 \le D \le 1{,}000{,}000{,}000$)가 주어진다.

$Q$개의 줄에 걸쳐 토르가 있는 행성에서 경로의 합이 $D$인 행성의 개수를 출력한다.

두 번째 질의에서 $4$번 위치에서 경로의 합이 $5$가 되는 행성은 $5$번 행성($E[4] + E[2] + E[5] = 5$)과 $3$번 행성($E[4] + E[2] + E[1] + E[3] = 5$)뿐이므로 답은 $2$이다.