Read problems statements in mandarin chinese, russian and vietnamese as well. 

Hussain is very bored, and has a lot of exams lined up next week. But he doesn't want to study. As usual, he decided to fail his exams and play with Hasan instead (who has already failed). Hussain invented this new game to play with Hasan. 

Hussain shows Hasan a multiset of integers. (A multiset is a collection of elements where there can be duplicates). In every move Hussain removes a maximum number from this multiset and divides it by 2 (integer division, which is rounded down).

If after dividing, the number is still positive (greater than 0) he re-inserts it back into the multiset. 

Before the start of the game, Hussain shows Hasan the numbers in his multiset.

Hussain asks Hasan, M questions. The i-th question will be denoted by Q[i], and Hasan must find the value of the number Hussain will be dividing (before he performs the division) after Q[i]-1 moves. That is, what is the value of the number on which the Q[i]-th division is performed?

Can you help Hasan and answer the queries?

------ Input ------ 

The first line contains 2 space separated integers N, M denoting the initial size of the multiset and the number of questions respectively.

The next line contains N space separated integers, the initial elements of the multiset.

Of the next M lines, the i-th line will contain Q[i].

------ Output ------ 

Output M lines, the i-th of which contains the answer for the i-th query.

------ Constraints ------ 

$1 ≤ N, M ≤ 10^{6}$
$The queries are given in chronological order. That is,  Q[i] > Q[i-1]  $
$Every element of the multiset will be a positive integer less than 2^{63}$
$It's guaranteed that the set will contain at least one element at the time of any query.$

----- Sample Input 1 ------ 
4 6
8 5 3 1
1
2
3
4
6
8
----- Sample Output 1 ------ 
8
5
4
3
2
1
----- explanation 1 ------ 
We show the multiset sorted at each step, for convenience.

Before any move, the multiset is (8, 5, 3, 1).
In the first move, 8 is removed, dived by 2, and thus becomes 4, and then re-inserted. So, the multiset, after the first move is (5, 4, 3, 1).
In the second move, 5 is removed and after division, it become 2, which is re-inserted. The multiset becomes (4, 3, 2, 1).
After the third move, the multiset becomes (3, 2, 2, 1).
After the fourth move, it becomes (2, 2, 1, 1).
After the fifth move, it becomes (2, 1, 1, 1).
After the sixth move, it becomes (1, 1, 1, 1).
In the seventh move, 1 is removed, and on division, it no longer is greater than 0. Hence, it is not re-inserted. So, after the seventh move, the multiset becomes (1, 1, 1).
After the eight move, the multiset becomes (1, 1).

The value being divided on the first move is 8. Hence the first output is 8.
The value being divided on the first move is 5. Hence the first output is 5.
The value being divided on the eight move is 1. Hence the last output is 1.

Difficulty: VERY_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
from collections import deque

def solve(l1, h, max1):
	q1 = deque(sorted(l1, reverse=True))
	q2 = deque()
	direction = 0
	for i in range(1, max1 + 1):
		if not q2 or q1[0] > q2[0]:
			ele = q1.popleft()
			if i in h:
				print(ele)
			ele = ele // 2
			if ele >= 1:
				q2.append(ele)
		else:
			ele = q2.popleft()
			if i in h:
				print(ele)
			ele = ele // 2
			if ele >= 1:
				q2.append(ele)
		if not q1:
			(q1, q2) = (q2, q1)
(n, m) = list(map(int, input().split()))
l1 = list(map(int, input().split()))
h = set([])
max1 = 0
for i in range(m):
	h_idx = int(input())
	h.add(h_idx)
	max1 = max(max1, h_idx)
solve(l1, h, max1)


from collections import deque

def divans(l, q, maxi):
	q1 = deque(l)
	q2 = deque()
	for i in range(1, maxi + 1):
		if not q2 or q1[0] > q2[0]:
			k = q1.popleft()
			if i in q:
				print(k)
			k //= 2
			if k >= 1:
				q2.append(k)
		else:
			k = q2.popleft()
			if i in q:
				print(k)
			k //= 2
			if k >= 1:
				q2.append(k)
		if not q1:
			(q1, q2) = (q2, q1)
(a, b) = list(map(int, input().split()))
l = list(map(int, input().split()))
l.sort(reverse=True)
maxi = 0
q = set()
for i in range(b):
	t = int(input())
	q.add(t)
	maxi = max(maxi, t)
divans(l, q, maxi)


from collections import deque

def calculate(arr, sets, max_):
	arr = deque(arr)
	queue = deque()
	for i in range(1, max_ + 1):
		if arr and (not queue or arr[-1] > queue[-1]):
			cur = arr.pop()
		else:
			cur = queue.pop()
		if i in sets:
			print(cur)
		cur //= 2
		if cur > 0:
			queue.appendleft(cur)
(n, m) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
arr.sort()
sets = set()
max_ = 0
for i in range(m):
	cur = int(input())
	sets.add(cur)
	max_ = max(max_, cur)
calculate(arr, sets, max_)


from collections import deque

def calculate(arr, sets, max_):
	arr = deque(arr)
	queue = deque()
	for i in range(1, max_ + 1):
		if not queue or arr[0] > queue[0]:
			cur = arr.popleft()
			if i in sets:
				print(cur)
			cur //= 2
			if cur > 0:
				queue.append(cur)
		else:
			cur = queue.popleft()
			if i in sets:
				print(cur)
			cur //= 2
			if cur > 0:
				queue.append(cur)
		if not arr:
			(arr, queue) = (queue, arr)
(n, m) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
arr.sort(reverse=True)
sets = set()
max_ = 0
for i in range(m):
	cur = int(input())
	sets.add(cur)
	max_ = max(max_, cur)
calculate(arr, sets, max_)


from collections import deque

def divans(l, q, maxi):
	q1 = deque(l)
	q2 = deque()
	for i in range(1, maxi + 1):
		if not q2 or q1[0] > q2[0]:
			k = q1.popleft()
			if i in q:
				print(k)
			k //= 2
			if k >= 1:
				q2.append(k)
		else:
			k = q2.popleft()
			if i in q:
				print(k)
			k //= 2
			if k >= 1:
				q2.append(k)
		if not q1:
			(q1, q2) = (q2, q1)
(n, m) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
arr.sort(reverse=True)
sets = set()
max_ = 0
for i in range(m):
	cur = int(input())
	sets.add(cur)
	max_ = max(max_, cur)
divans(arr, sets, max_)


from collections import deque

def solveQ(arr, queries, maxT):
	q1 = deque(sorted(arr, reverse=True))
	q2 = deque()
	for i in range(1, maxT + 1):
		if not q2 or q1[0] > q2[0]:
			e = q1.popleft()
		else:
			e = q2.popleft()
		if i in queries:
			print(e)
		e //= 2
		if e > 0:
			q2.append(e)
		if not q1:
			(q1, q2) = (q2, q1)
(n, m) = map(int, input().split())
multi = [int(x) for x in input().split()]
queries = [int(input()) for _ in range(m)]
maxQ = max(queries)
solveQ(multi, set(queries), maxQ)


from collections import deque

def solution(multiset, questions, maxq):
	to_print = []
	q1 = deque(sorted(multiset, reverse=True))
	q2 = deque()
	for i in range(1, maxq + 1):
		if not q2 or q1[0] > q2[0]:
			element = q1.popleft()
		else:
			element = q2.popleft()
		if i in questions:
			to_print.append(element)
		element = element >> 1
		if element > 0:
			q2.append(element)
		if not q1:
			(q1, q2) = (q2, q1)
	print('\n'.join(map(str, to_print)))

def main():
	(n, m) = map(int, input().split())
	multiset = list(map(int, input().split()))
	questions = [int(input()) for _ in range(m)]
	maxq = questions[-1]
	solution(multiset, set(questions), maxq)
main()


from collections import deque

def solveQueue(arr, queries, maxTurn):
	flag = False
	for j in range(1, maxTurn + 1):
		if not q1:
			front2 = q2[0]
			if j in queries:
				print(front2)
			q2.popleft()
			front2 //= 2
			if front2 > 0:
				q2.append(front2)
		elif not q2 or q1[0] > q2[0]:
			front1 = q1[0]
			if j in queries:
				print(front1)
			q1.popleft()
			front1 //= 2
			if front1 > 0:
				q2.append(front1)
		else:
			front2 = q2[0]
			if j in queries:
				print(front2)
			q2.popleft()
			front2 //= 2
			if front2 > 0:
				q2.append(front2)
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
q1 = deque(sorted(arr, reverse=True))
q2 = deque()
queries = set()
maxTurn = 0
for _ in range(m):
	query = int(input())
	queries.add(query)
	maxTurn = max(maxTurn, query)
solveQueue(arr, queries, maxTurn)


from collections import deque

def solve(l, h, max1):
	q1 = deque(l)
	q2 = deque()
	for i in range(1, max1 + 1):
		if not q2 or q1[0] > q2[0]:
			temp = q1.popleft()
			if i in h:
				print(temp)
			temp = temp // 2
			if temp > 0:
				q2.append(temp)
		else:
			temp = q2.popleft()
			if i in h:
				print(temp)
			temp = temp // 2
			if temp > 0:
				q2.append(temp)
		if not q1:
			(q1, q2) = (q2, q1)
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
h = set()
max1 = 0
for i in range(m):
	q = int(input())
	h.add(q)
	max1 = max(max1, q)
solve(l, h, max1)


from collections import deque

def use_q(l, q, mx):
	l_1 = deque(sorted(l, reverse=True))
	l_2 = deque()
	for i in range(1, mx + 1):
		if not l_2 or l_1[0] > l_2[0]:
			t_2 = l_1.popleft()
			if i in q:
				print(t_2)
			t_2 = t_2 // 2
			if t_2 > 0:
				l_2.append(t_2)
		else:
			t_3 = l_2.popleft()
			if i in q:
				print(t_3)
			t_3 = t_3 // 2
			if t_3 > 0:
				l_2.append(t_3)
		if not l_1:
			(l_1, l_2) = (l_2, l_1)
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
q = set([])
m_1 = -1
for i in range(m):
	t_4 = int(input())
	q.add(t_4)
	m_1 = max(m_1, t_4)
use_q(l, q, m_1)


from collections import deque

def use_q(l, q, mx):
	l1 = deque(sorted(l, reverse=True))
	l2 = deque()
	for i in range(1, mx + 1):
		if not l2 or l1[0] > l2[0]:
			t = l1.popleft()
			if i in q:
				print(t)
			t //= 2
			if t > 0:
				l2.append(t)
		else:
			t = l2.popleft()
			if i in q:
				print(t)
			t //= 2
			if t > 0:
				l2.append(t)
		if not l1:
			(l1, l2) = (l2, l1)
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
q = set([])
m_1 = -1
for i in range(m):
	t_4 = int(input())
	q.add(t_4)
	m_1 = max(m_1, t_4)
use_q(l, q, m_1)


from time import time
from bisect import insort
from collections import deque

def main2():
	(n, m) = map(int, input().strip().split())
	arr1 = list(map(int, input().strip().split()))
	quest = [int(input().strip()) for x in range(m)]
	ans = [0] * 63000005
	arr2 = deque()
	arr1.sort(reverse=True)
	arr1 = deque(arr1)
	i = -1
	while True:
		if not arr1:
			if not arr2:
				break
			ele = arr2.popleft()
		elif not arr2:
			ele = arr1.popleft()
		elif arr1[0] >= arr2[0]:
			ele = arr1.popleft()
		else:
			ele = arr2.popleft()
		i += 1
		ans[i] = ele
		ele //= 2
		if ele > 0:
			arr2.append(ele)
	for q in quest:
		print(ans[q - 1])

def main():
	(n, m) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	quest = [int(input().strip()) for x in range(m)]
	ans = list()
	arr.sort()
	while arr:
		ele = arr[-1]
		ans.append(ele)
		ele //= 2
		arr.pop(-1)
		if ele > 0:
			insort(arr, ele)
	for q in quest:
		print(ans[q - 1])
main2()


from bisect import insort
from collections import deque

def main():
	(n, m) = map(int, input().split())
	a1 = list(map(int, input().split()))
	q = [int(input()) for x in range(m)]
	ans = [0] * 63000005
	a2 = deque()
	a1.sort(reverse=True)
	a1 = deque(a1)
	i = -1
	while True:
		if not a1:
			if not a2:
				break
			x = a2.popleft()
		elif not a2:
			x = a1.popleft()
		elif a1[0] >= a2[0]:
			x = a1.popleft()
		else:
			x = a2.popleft()
		i += 1
		ans[i] = x
		x //= 2
		if x > 0:
			a2.append(x)
	for i in q:
		print(ans[i - 1])
main()


from collections import deque as dq

def que(s, c, t):
	a = dq(sorted(s, reverse=True))
	b = dq()
	for i in range(1, c + 1):
		if not b or a[0] > b[0]:
			f = a.popleft()
			if i in t:
				print(f)
			f = f // 2
			if f >= 1:
				b.append(f)
		else:
			f = b.popleft()
			if i in t:
				print(f)
			f = f // 2
			if f >= 1:
				b.append(f)
		if not a:
			(a, b) = (b, a)
(N, M) = map(int, input().split())
s = list(map(int, input().split()))
t = set([])
c = 0
for i in range(M):
	r = int(input())
	if r > c:
		c = r
	t.add(r)
que(s, c, t)


from collections import deque

def que(arr, max, queries):
	q1 = deque(sorted(arr, reverse=True))
	q2 = deque()
	for i in range(1, max + 1):
		if not q2 or q1[0] > q2[0]:
			ele = q1.popleft()
			if i in queries:
				print(ele)
			ele = ele // 2
			if ele >= 1:
				q2.append(ele)
		else:
			ele = q2.popleft()
			if i in queries:
				print(ele)
			ele = ele // 2
			if ele >= 1:
				q2.append(ele)
		if not q1:
			(q1, q2) = (q2, q1)
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
queries = set([])
max = 0
for i in range(m):
	query = int(input())
	if query > max:
		max = query
	queries.add(query)
que(arr, max, queries)


from collections import deque

def solve(nums, queries, maxi):
	q1 = deque(sorted(nums, reverse=True))
	q2 = deque()
	direction = 0
	for i in range(1, maxi + 1):
		if not q2 or q1[0] > q2[0]:
			ele = q1.popleft()
			if i in queries:
				print(ele)
			ele = ele // 2
			if ele >= 1:
				q2.append(ele)
		else:
			ele = q2.popleft()
			if i in queries:
				print(ele)
			ele = ele // 2
			if ele >= 1:
				q2.append(ele)
		if not q1:
			(q1, q2) = (q2, q1)
(n, m) = list(map(int, input().split()))
nums = list(map(int, input().split()))
queries = set([])
maxi = 0
for i in range(m):
	query_idx = int(input())
	queries.add(query_idx)
	maxi = max(maxi, query_idx)
solve(nums, queries, maxi)