배열에서 개구리 뛰기

디마는 초보 프로그래머다. 그는 작업하면서 배열에서 두 번째마다 원소를 하나씩 제거하는 연산을 계속 반복해야 한다. 어느 날 디마는 이 문제의 평범한 풀이가 지루해져서 다음과 같은 독특한 알고리즘을 떠올렸다.

처음에 배열에는 1부터 $n$까지의 수가 들어 있고, 수 $i$는 인덱스 $2i - 1$인 칸에 놓여 있다(인덱스는 1부터 시작한다). 배열의 나머지 칸은 모두 비어 있다. 매 단계마다 디마는 비어 있지 않은 칸 중 인덱스가 가장 큰 칸을 고르고, 그 칸에 적힌 수를 선택한 칸보다 왼쪽에 있는 가장 가까운 빈 칸으로 옮긴다. 모든 수가 배열의 처음 $n$개 칸에 놓일 때까지 이 과정을 반복한다. 예를 들어 $n = 4$이면 배열은 다음과 같이 변한다.

디마의 알고리즘이 끝난 뒤 인덱스 $x$($1 \leq x \leq n$)인 칸에 들어 있는 수를 구하는 프로그램을 작성하라.

첫 줄에 두 정수 $n$과 $q$($1 \leq n \leq 10^{18}$, $1 \leq q \leq 200\,000$)가 주어진다. 이는 배열의 원소 개수와 질의 개수이다. 다음 $q$개 줄에는 각각 정수 $x_i$($1 \leq x_i \leq n$)가 주어지며, 이는 칸의 인덱스이다.

각 질의마다 알고리즘이 끝난 뒤 해당 칸에 들어 있는 수를 한 줄에 하나씩 출력한다.