This is an interactive problem. Refer to the Interaction section below for better understanding.

Ithea and Chtholly want to play a game in order to determine who can use the kitchen tonight.

<image>

Initially, Ithea puts n clear sheets of paper in a line. They are numbered from 1 to n from left to right.

This game will go on for m rounds. In each round, Ithea will give Chtholly an integer between 1 and c, and Chtholly needs to choose one of the sheets to write down this number (if there is already a number before, she will erase the original one and replace it with the new one).

Chtholly wins if, at any time, all the sheets are filled with a number and the n numbers are in non-decreasing order looking from left to right from sheet 1 to sheet n, and if after m rounds she still doesn't win, she loses the game.

Chtholly really wants to win the game as she wants to cook something for Willem. But she doesn't know how to win the game. So Chtholly finds you, and your task is to write a program to receive numbers that Ithea gives Chtholly and help her make the decision on which sheet of paper write this number.

Input

The first line contains 3 integers n, m and c (<image>, <image> means <image> rounded up) — the number of sheets, the number of rounds and the largest possible number Ithea can give to Chtholly respectively. The remaining parts of input are given throughout the interaction process.

Interaction

In each round, your program needs to read one line containing a single integer pi (1 ≤ pi ≤ c), indicating the number given to Chtholly.

Your program should then output a line containing an integer between 1 and n, indicating the number of sheet to write down this number in.

After outputting each line, don't forget to flush the output. For example: 

  * fflush(stdout) in C/C++; 
  * System.out.flush() in Java; 
  * sys.stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * See the documentation for other languages. 



If Chtholly wins at the end of a round, no more input will become available and your program should terminate normally. It can be shown that under the constraints, it's always possible for Chtholly to win the game.

Example

Input

2 4 4
2
1
3


Output

1
2
2

Note

In the example, Chtholly initially knew there were 2 sheets, 4 rounds and each number was between 1 and 4. She then received a 2 and decided to write it in the 1st sheet. Then she received a 1 and wrote it in the 2nd sheet. At last, she received a 3 and replaced 1 with 3 in the 2nd sheet. At this time all the sheets were filled with a number and they were non-decreasing, so she won the game. 

Note that it is required that your program terminate immediately after Chtholly wins and do not read numbers from the input for the remaining rounds. If not, undefined behaviour may arise and it won't be sure whether your program will be accepted or rejected. Also because of this, please be careful when hacking others' codes. In the sample, Chtholly won the game after the 3rd round, so it is required that your program doesn't read the number of the remaining 4th round.

The input format for hacking: 

  * The first line contains 3 integers n, m and c; 
  * The following m lines each contains an integer between 1 and c, indicating the number given to Chtholly in each round.

Difficulty: HARD
Tags: Sorting

Constructive algorithms

Game theory

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import sys
(n, m, c) = map(int, input().split())
free = n
nums = [0] * n
for i in range(m):
	pi = int(input())
	if pi > c // 2:
		current = n - 1
		while nums[current] > 0 and nums[current] >= pi and (current >= 0):
			current -= 1
		if current == -1:
			current = 0
		if nums[current] == 0:
			free -= 1
		nums[current] = pi
		print(current + 1)
	else:
		current = 0
		while current < n and nums[current] > 0 and (nums[current] <= pi):
			current += 1
		if current == n:
			current = n - 1
		if nums[current] == 0:
			free -= 1
		nums[current] = pi
		print(current + 1)
	if free == 0:
		break


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
(N, M, C) = map(int, input().split())
ans = [0] * (N + 1)
(ls, le) = (1, N + 1)
(rs, re) = (N // 2 + 1, N + 1)
for _ in range(M):
	p = int(input())
	ii = -1
	if p < C // 2 + 1:
		for i in range(1, N + 1):
			if ans[i] == 0 or ans[i] > p:
				ii = i
				break
	else:
		for i in range(N, 0, -1):
			if ans[i] == 0 or ans[i] < p:
				ii = i
				break
	ans[ii] = p
	print(ii)
	sys.stdout.flush()
	if all((x > 0 for x in ans[1:])):
		exit(0)


import sys

def output(n):
	print(n)
	sys.stdout.flush()
(n, m, c) = map(int, input().split())
arr = [0 for _ in range(n)]
l = -1
r = n
cnt = 0
while cnt < n:
	p = int(input())
	if p <= (c + 1) // 2:
		for i in range(0, r):
			if arr[i] == 0:
				l += 1
				output(i + 1)
				arr[i] = p
				break
			elif p < arr[i]:
				output(i + 1)
				arr[i] = p
				break
	else:
		for i in range(n - 1, l, -1):
			if arr[i] == 0:
				r -= 1
				output(i + 1)
				arr[i] = p
				break
			elif arr[i] < p:
				output(i + 1)
				arr[i] = p
				break
	if r - l == 1:
		break


(n, m, c) = map(int, input().split())
a = [0] * n
while a.count(0):
	x = int(input())
	if x > c // 2:
		i = n - 1
		while a[i] >= x:
			i -= 1
		a[i] = x
	else:
		i = 0
		while a[i] and a[i] <= x:
			i += 1
		a[i] = x
	print(i + 1)


def main():
	(n, m, c) = map(int, input().split())
	middle = (c + 1) // 2 * 2 + 1
	xs = [middle for _ in range(n)]

	def value(a, b):
		if a > middle:
			return b - a
		elif a < middle:
			return a - b
		return c
	for _ in range(m):
		sheet = int(input().strip()) * 2
		best_i = -1
		best_value = -1
		for i in range(n):
			if (i == 0 or xs[i - 1] <= sheet) and (i == n - 1 or sheet <= xs[i + 1]):
				tmp_value = value(xs[i], sheet)
				if tmp_value > best_value:
					best_value = tmp_value
					best_i = i
		xs[best_i] = sheet
		print(best_i + 1, flush=True)
		if not any((x == middle for x in xs)):
			break
main()


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
(n, m, c) = map(int, input().split())
l = 0
r = n - 1
ans = [0 for i in range(n)]
while l <= r:
	x = int(input())
	if x <= c / 2:
		i = 0
		while i < l and ans[i] <= x:
			i += 1
		ans[i] = x
		print(i + 1)
		sys.stdout.flush()
		if i == l:
			l += 1
	else:
		i = n - 1
		while i > r and ans[i] >= x:
			i -= 1
		ans[i] = x
		print(i + 1)
		sys.stdout.flush()
		if i == r:
			r -= 1


import sys
import math
(N, M, C) = map(int, input().split())
mid = C // 2
res = []
for i in range(0, N):
	res.append(0)
(l, r) = (0, N - 1)
for i in range(0, M):
	val = int(input())
	pos = 0
	if val <= mid:
		for j in range(0, l + 1):
			if res[j] == 0 or val < res[j]:
				res[j] = val
				pos = j
				break
		if pos == l:
			l += 1
	else:
		for j in range(N - 1, r - 1, -1):
			if res[j] == 0 or val > res[j]:
				res[j] = val
				pos = j
				break
		if pos == r:
			r -= 1
	print('%d' % (pos + 1))
	sys.stdout.flush()
	if l > r:
		exit()


import sys
(n, m, c) = [int(x) for x in input().split()]
l = 0
r = 0
smalldata = [c + 1] * n
largedata = [-1] * n
small = c // 2
large = c - small
for i in range(m):
	num = int(input())
	if num <= small:
		ind = 0
		while smalldata[ind] <= num:
			ind += 1
		smalldata[ind] = num
		l = 1
		while l < n and smalldata[l] != c + 1 and (smalldata[l - 1] <= smalldata[l]):
			l += 1
	else:
		ind = n - 1
		while largedata[ind] >= num:
			ind -= 1
		largedata[ind] = num
		r = 1
		while r < n and largedata[-r - 1] != -1 and (largedata[-r] >= largedata[-r - 1]):
			r += 1
	print(ind + 1)
	sys.stdout.flush()
	if l + r >= n:
		break


import bisect
import sys

def output(n):
	print(n)
	sys.stdout.flush()
(n, m, c) = map(int, input().split())
al = [c + 1 for _ in range(n)]
ar = [0 for _ in range(n)]
l = -1
r = n
while 1 < r - l:
	p = int(input())
	if p <= (c + 1) // 2:
		i = bisect.bisect_right(al, p)
		output(i + 1)
		if al[i] == c + 1:
			l += 1
		al[i] = p
	else:
		i = bisect.bisect_right(ar, -p)
		output(n - i)
		if ar[i] == 0:
			r -= 1
		ar[i] = -p


import sys
(n, m, c) = map(int, input().split())
l = [0 for _ in range(n)]
for j in range(m):
	p = int(input())
	if p > c // 2:
		i = n - 1
		while i > 0 and p <= l[i]:
			i -= 1
		l[i] = p
	else:
		i = 0
		while l[i] != 0 and i < n - 1 and (p >= l[i]):
			i += 1
		l[i] = p
	print(i + 1)
	sys.stdout.flush()
	if 0 not in l and sorted(l) == l:
		break


import sys
from bisect import bisect_left, bisect_right
from itertools import *

class Antiint:

	def __init__(self, i):
		self.i = i

	def __lt__(self, other):
		return self.i > other.i

	def __eq__(self, other):
		return self.i == other.i
(n, m, c) = map(int, input().split())
down_c = c // 2
paper_left = [0]
paper_right = [Antiint(c + 1)]
while len(paper_left) + len(paper_right) < n + 2:
	next = int(input())
	if next <= down_c:
		if next >= paper_left[-1]:
			paper_left.append(next)
			print(len(paper_left) - 1)
		else:
			index = bisect_right(paper_left, next)
			paper_left[index] = next
			print(index)
	elif next <= paper_right[-1].i:
		paper_right.append(Antiint(next))
		print(n + 2 - len(paper_right))
	else:
		index = bisect_right(paper_right, Antiint(next))
		paper_right[index] = Antiint(next)
		print(n + 1 - index)
	sys.stdout.flush()


import sys
(n, m, c) = map(int, input().split())
a = []
for i in range(n + 1):
	a.append(0)
cnt = 0
while cnt < n:
	i = 0
	x = int(input())
	if x * 2 <= c:
		i = 1
		while a[i] and a[i] <= x:
			i += 1
	else:
		i = n
		while a[i] and a[i] >= x:
			i -= 1
	if a[i] == 0:
		cnt += 1
	a[i] = x
	print(i)
	sys.stdout.flush()


def get_int(string, n):
	i = j = k = 0
	for s in string:
		k += 1
	for s in string:
		if i == n - 1:
			break
		if s == ' ':
			i += 1
		j += 1
	i = 0
	while j < k:
		if string[j] == ' ':
			break
		i = 10 * i + int(string[j])
		j += 1
	return i

def check_order(ls, n):
	for i in ls:
		if i == None:
			return 0
	for i in range(0, n - 1):
		if ls[i] > ls[i + 1]:
			return -1
	return 1

def forward(p, ls, n):
	for i in range(0, n):
		if ls[i] == None:
			ls[i] = p
			print(i + 1)
			return 0
		if ls[i] > p:
			ls[i] = p
			print(i + 1)
			return 0

def reverse(p, ls, n):
	for i in range(0, n):
		if ls[n - 1 - i] == None:
			ls[n - 1 - i] = p
			print(n - i)
			return 0
		elif ls[n - 1 - i] < p:
			ls[n - i - 1] = p
			print(n - i)
			return 0
x = input()
n = get_int(x, 1)
m = get_int(x, 2)
c = get_int(x, 3)
ls = []
for i in range(0, n):
	ls += [None]
for i in range(0, m):
	p = int(input())
	if p > c / 2:
		reverse(p, ls, n)
	else:
		forward(p, ls, n)
	if check_order(ls, n) == 1:
		break