Misha was interested in water delivery from childhood. That's why his mother sent him to the annual Innovative Olympiad in Irrigation (IOI). Pupils from all Berland compete there demonstrating their skills in watering. It is extremely expensive to host such an olympiad, so after the first $n$ olympiads the organizers introduced the following rule of the host city selection.

The host cities of the olympiads are selected in the following way. There are $m$ cities in Berland wishing to host the olympiad, they are numbered from $1$ to $m$. The host city of each next olympiad is determined as the city that hosted the olympiad the smallest number of times before. If there are several such cities, the city with the smallest index is selected among them.

Misha's mother is interested where the olympiad will be held in some specific years. The only information she knows is the above selection rule and the host cities of the first $n$ olympiads. Help her and if you succeed, she will ask Misha to avoid flooding your house.


-----Input-----

The first line contains three integers $n$, $m$ and $q$ ($1 \leq n, m, q \leq 500\,000$) — the number of olympiads before the rule was introduced, the number of cities in Berland wishing to host the olympiad, and the number of years Misha's mother is interested in, respectively.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq m$), where $a_i$ denotes the city which hosted the olympiad in the $i$-th year. Note that before the rule was introduced the host city was chosen arbitrarily.

Each of the next $q$ lines contains an integer $k_i$ ($n + 1 \leq k_i \leq 10^{18}$) — the year number Misha's mother is interested in host city in.


-----Output-----

Print $q$ integers. The $i$-th of them should be the city the olympiad will be hosted in the year $k_i$.


-----Examples-----
Input
6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16

Output
4
3
4
2
3
4
1
2
3
4

Input
4 5 4
4 4 5 1
15
9
13
6

Output
5
3
3
3



-----Note-----

In the first example Misha's mother is interested in the first $10$ years after the rule was introduced. The host cities these years are 4, 3, 4, 2, 3, 4, 1, 2, 3, 4.

In the second example the host cities after the new city is introduced are 2, 3, 1, 2, 3, 5, 1, 2, 3, 4, 5, 1.

Difficulty: HARD
Tags: Sorting

Amortized analysis

Implementation

Tree algorithms

Data structures
Skill types: Data structures

Sorting

Amortized analysis

Starter code:

Solutions:
from bisect import bisect_left as bl
import sys
(N, M, Q) = map(int, sys.stdin.readline().split())
count = [0] * (M + 1)
A = []
for a in sys.stdin.readline().split():
	a = int(a)
	A.append(count[a] * M + a)
	count[a] += 1
A.sort()
A = [a - i for (i, a) in enumerate(A, 1)]
for _ in range(Q):
	q = int(sys.stdin.readline()) - N
	if q > A[-1]:
		q += N
	else:
		q += bl(A, q)
	sys.stdout.write(f'{(q - 1) % M + 1}\n')


from bisect import bisect_left
from sys import stdin, stdout
(n, m, q) = map(int, stdin.readline().split())
count = [0] * (m + 1)
a = []
for el in stdin.readline().split():
	el = int(el)
	a.append(count[el] * m + el)
	count[el] += 1
a.sort()
a = [el - (i + 1) for (i, el) in enumerate(a)]
while q:
	t = int(stdin.readline()) - n
	if t > a[n - 1]:
		t += n
	else:
		t += bisect_left(a, t)
	stdout.write(f'{(t - 1) % m + 1}\n')
	q -= 1


import operator as op
import os
import sys
from bisect import bisect_left, bisect_right, insort
from functools import reduce
from io import BytesIO, IOBase
from itertools import chain, repeat, starmap

def main():
	input = sys.stdin.buffer.readline
	(n, m, q) = map(int, input().split())
	a = [int(x) for x in input().split()]
	counter = [0] * m
	for ai in a:
		counter[ai - 1] += 1
	count_order = sorted(range(m), key=lambda x: counter[x])
	years = [0] * m
	for i in range(m - 1):
		diff = counter[count_order[i + 1]] - counter[count_order[i]]
		years[i + 1] = years[i] + diff * (i + 1)
	max_k = max(counter) * m - sum(counter)
	k = [int(input()) - n for _ in range(q)]
	k_order = sorted(range(q), key=lambda x: k[x])
	sortedlist = SortedList()
	(res, idx) = ([0] * q, 0)
	for i in range(q):
		ki = k[k_order[i]]
		if ki > max_k:
			res[k_order[i]] = (ki - max_k - 1) % m + 1
		else:
			while years[idx] < ki:
				sortedlist.add(count_order[idx])
				idx += 1
			ki -= years[idx - 1] + 1
			ki %= idx
			res[k_order[i]] = sortedlist[ki] + 1
	print(*res, sep='\n')

class SortedList:
	DEFAULT_LOAD_FACTOR = 500

	def __init__(self, iterable=None):
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self.update(iterable)

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self.clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]

	def __contains__(self, value):
		_maxes = self._maxes
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def remove(self, value):
		_maxes = self._maxes
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(op.add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 1 << (len(row1) - 1).bit_length()
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(op.add, zip(head, tail)))
			tree.append(row)
		reduce(list.__iadd__, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self.clear()
				elif self._len <= 8 * (stop - start):
					values = self.__getitem__(slice(None, start))
					if stop < self._len:
						values += self.__getitem__(slice(stop, None))
					self.clear()
					return self.update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(list.__iadd__, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				if start_pos == stop_pos:
					return _lists[start_pos][start_idx:stop_idx]
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(list.__iadd__, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self.__getitem__(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self.__getitem__(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		pos = bisect_left(self._maxes, value)
		return self._len if pos == len(self._maxes) else self._loc(pos, bisect_left(self._lists[pos], value))

	def bisect_right(self, value):
		pos = bisect_right(self._maxes, value)
		return self._len if pos == len(self._maxes) else self._loc(pos, bisect_right(self._lists[pos], value))

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def __copy__(self):
		return self.__class__(self)

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=0, stop=None):
		_len = self._len
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		elif start <= self.bisect_right(value) - 1:
			return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(list.__iadd__, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self.update(other)
		return self

	def __mul__(self, num):
		values = reduce(list.__iadd__, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(list.__iadd__, self._lists, []) * num
		self.clear()
		self.update(values)
		return self

	def __make_cmp(seq_op):

		def comparer(self, other):
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is op.eq:
					return False
				if seq_op is op.ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		comparer.__name__ = '__{0}__'.format(seq_op.__name__)
		return comparer
	__eq__ = __make_cmp(op.eq)
	__ne__ = __make_cmp(op.ne)
	__lt__ = __make_cmp(op.lt)
	__gt__ = __make_cmp(op.gt)
	__le__ = __make_cmp(op.le)
	__ge__ = __make_cmp(op.ge)
	__make_cmp = staticmethod(__make_cmp)

	def __repr__(self):
		return 'SortedList({0})'.format(reduce(list.__iadd__, self._lists, []))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()