15909번 - 토르의 여행

토르는 인피니티 스톤이 있는 행성에 대한 정보를 얻었다. 마블의 모든 행성은 포화 완전이진트리 형태로 연결되어 있으며, 각 행성은 에너지값 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 ≤ N ≤ 17)이 주어진다. 두 번째 줄에는 각 행성의 에너지 E_i(-1,000,000,000 ≤ E_i ≤ 1,000,000,000)가 (2^N)-1 개만큼 주어진다. 세 번째 줄에는 Q(1 ≤ Q ≤ 100,000)가 주어진다. 다음 Q 줄에 걸쳐서 현재 토르가 위치한 행성의 번호 A(1 ≤ A ≤ 2^N-1)와 현재 위치에서 인피니티 스톤이 존재할 가능성이 있는 행성까지의 경로의 합 D(-1,000,000,000 ≤ D ≤ 1,000,000,000)가 주어진다.

Q 줄에 걸쳐서 현재 토르가 위치한 행성에서 인피니티 스톤이 있을 수 있는 행성의 개수를 출력한다.

2번째 예제 케이스에서 4번 위치에서 경로의 합이 5가 되는 행성은 5번 행성(E[4] + E[2] + E[5] = 5)과 3번 행성(E[4] + E[2] + E[1] + E[3] = 5) 2개밖에 존재하지 않는다.