때는 30XX 년. 과학자·기술자의 끊임없는 노력으로 우주의 다른 행성 간의 교류가 활발히 이루어지게 되었다.

비버 비타로는 이성인에게 지구의 음식을 소개하는 앰배서더를 맡고 있으며, 오늘 오후 1시에 JOI 별을 향해 출발할 예정이다.

이번 JOI 성인에게 소개하는 음식 중 하나로서 잘라낸 카스테라가 준비되어 있다. 카스텔라는 밀가루에 닭고기 달걀, 설탕, 물을 넣고 스폰지 모양으로 통통하게 구운 과자이다.

카스텔라는 가로로 길어진 직육면체의 형태를 하고 있으며, 종 방향의 틈을 따라 N개의 조각으로 분할되어 있다. 왼쪽에서 i 번째 (1≤i≤N) 조각의 길이는 정수 A_i입니다.

마지막으로 JOI 성인은 짝수에 혐오감을 보인다는 것이 밝혀졌다. 따라서 해결책으로 길이가 짝수인 조각이 없을 때까지 다음 일련의 작업을 반복하기로 결정했습니다.

1. 길이가 짝수 조각 중 가장 오른쪽에 있는 것을 선택합니다.

2. 선택한 조각을 세로로 자르고 이등분한다. 즉, 선택한 조각의 길이를 k로 설정하면 위치를 변경하지 않고 길이 \frac k2 조각으로 나눕니다.

작업이 올바르게 수행되었는지 확인하기 위해 Bitaro는 Q 개의 질문을 준비했습니다. j 번째 (1≤j≤Q)의 질문은 다음과 같습니다.

• 모든 작업이 끝나면 왼쪽에서 X_j 번째 조각의 길이는 무엇입니까?

카스텔라와 질문에 대한 정보가 주어지면 각 질문에 대한 답변을 찾는 프로그램을 작성하십시오.

인터캐스텔러 timer 2s memory 1024MB

인터캐스텔러 2s 1024MB