Intercastellar

30XX년, 과학자와 기술자들의 끊임없는 노력 덕분에 서로 다른 행성 사이의 교류가 매우 활발해졌다. 비타로는 교환 프로그램의 대사로 일하는 비버이다. 그의 임무는 지구의 음식을 여러 행성의 주민에게 소개하는 것이다. 그는 오후 1시에 JOI 행성으로 떠난다.

지금 비타로는 JOI 행성의 주민에게 카스텔라를 소개하려고 한다. 카스텔라는 이미 여러 조각으로 잘려 있다. 카스텔라는 밀가루, 달걀, 설탕, 물엿으로 만든 구운 스펀지 케이크이다.

카스텔라의 모양은 가로로 긴 직육면체이다. $N$조각으로 잘려 있다. 왼쪽에서 $i$번째 조각($1 ≤ i ≤ N$)의 길이는 정수 $A\_i$이다.

몇 분 전, JOI 행성의 주민이 짝수 길이를 싫어한다는 사실이 밝혀졌다. 이 문제를 해결하기 위해, 짝수 길이 조각이 사라질 때까지 다음 작업을 순서대로 수행한다.

1. 짝수 길이 조각 중 가장 오른쪽에 있는 조각을 고른다.
2. 고른 조각을 같은 길이의 두 조각으로 자른다. 즉, 고른 조각의 길이가 $k$이면 길이 $\frac{k}{2}$인 두 조각으로 자른다. 조각의 위치는 움직이지 않는다.

작업이 올바르게 수행되는지 확인하기 위해 비타로는 $Q$개의 질문을 한다. $j$번째 질문($1 ≤ j ≤ Q$)은 다음과 같다.

• 모든 작업이 끝난 후, 왼쪽에서 $X\_j$번째 조각의 길이는 얼마인가?

카스텔라의 정보와 질문이 주어졌을 때, 질문에 답하는 프로그램을 작성하시오.

다음 데이터를 표준 입력에서 읽는다. 주어지는 값은 모두 정수이다.

\begin{align\*} & N \\ & A\_1 \\ & A\_2 \\ & \vdots \\ & A\_N \\ & Q \\ & X\_1 \\ & X\_2 \\ & \vdots \\ & X\_Q\end{align\*}

$Q$개의 줄을 표준 출력에 쓴다. $j$번째 줄($1 ≤ j ≤ Q$)에는 $j$번째 질문의 답이 들어가야 한다.

• $1 ≤ N ≤ 200\,000$.
• $1 ≤ A\_i ≤ 1\,000\,000\,000$ ($1 ≤ i ≤ N$).
• $1 ≤ Q ≤ 200\,000$.
• $1 ≤ X\_j ≤ 1\,000\,000\,000\,000\,000$ ($= 10^{15}$) ($1 ≤ j ≤ Q$).
• $X\_j ≤ X\_{j+1}$ ($1 ≤ j ≤ Q - 1$).
• 모든 작업이 끝난 후, 카스텔라는 적어도 $X\_Q$조각으로 잘려 있다.