Problem: A parking lot in the City consists of n parking spaces, standing in a line. The parking spaces are numbered from 1 to n from left to right. 

When a car arrives at the lot, the operator determines an empty parking space for it. For the safety's sake the chosen place should be located as far from the already occupied places as possible. That is, the closest occupied parking space must be as far away as possible. If there are several such places, then the operator chooses the place with the minimum index from them. If all parking lot places are empty, then the car gets place number 1.

We consider the distance between the i-th and the j-th parking spaces equal to 4·|i - j| meters.

You are given the parking lot records of arriving and departing cars in the chronological order. For each record of an arriving car print the number of the parking lot that was given to this car.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 2·105) — the number of parking places and the number of records correspondingly. 

Next m lines contain the descriptions of the records, one per line. The i-th line contains numbers ti, idi (1 ≤ ti ≤ 2; 1 ≤ idi ≤ 106). If ti equals 1, then the corresponding record says that the car number idi arrived at the parking lot. If ti equals 2, then the corresponding record says that the car number idi departed from the parking lot. 

Records about arriving to the parking lot and departing from the parking lot are given chronologically. All events occurred consecutively, no two events occurred simultaneously.

It is guaranteed that all entries are correct: 

  * each car arrived at the parking lot at most once and departed from the parking lot at most once, 
  * there is no record of a departing car if it didn't arrive at the parking lot earlier, 
  * there are no more than n cars on the parking lot at any moment. 



You can consider the cars arbitrarily numbered from 1 to 106, all numbers are distinct. Initially all places in the parking lot are empty.

Output

For each entry of an arriving car print the number of its parking space. Print the numbers of the spaces in the order, in which the cars arrive to the parking lot.

Examples

Input

7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8


Output

1
7
4
2
7
4
1
3

Solution (in JAVA):

Solution:
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.TreeSet;

/**
 * Actual solution is at the top, in class Solver
 */
public class Main implements Runnable {
	private static String[] args;

	public static void main(String[] args) {
		Main.args = args;
		new Thread(null, new Main(), "MyRunThread", 1 << 26).start();
	}

	@Override
	public void run() {
		long time_beg = -1;
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		if (args.length > 0 && args[0].equals("outside")) {
			time_beg = System.currentTimeMillis();
			try {
				inputStream = new FileInputStream("IO/in.txt");
//				outputStream = new FileOutputStream("IO/out.txt");
			} catch (Exception e) {
				System.err.println(e);
				System.exit(1);
			}
		} else {
			try {
//				inputStream = new FileInputStream("file_name");
//				outputStream = new FileOutputStream("file_name");
			} catch (Exception e) {
				System.err.println(e);
				System.exit(1);
			}
		}

		Solver s = new Solver();
		s.in = new InputReader(inputStream);
		s.out = new OutputWriter(outputStream);
		if (args.length > 0 && args[0].equals("outside")) {
			s.debug = new DebugWriter(s.out);
		}

		s.solve();
		s.out.close();

		if (args.length > 0 && args[0].equals("outside")) {
			s.debug.close();
			System.err.printf("*** Total time: %.3f ***\n", (System.currentTimeMillis() - time_beg) / 1000.0);
		}
	}
}

final class Solver {
	InputReader in;
	OutputWriter out;
	DebugWriter debug;

	public void solve() {
		n = in.readInt();
		int q = in.readInt();

		set = new TreeSet<>();
		leftID = new HashMap<>();
		rightID = new HashMap<>();
		size = new HashMap<>();
		startIndex = new HashMap<>();
		goodSize = new HashMap<>();

		left = 0;
		length = -1;
		right = -1;

		while (q-- > 0) {
			int t = in.readInt();
			int ID = in.readInt();
			if (t == 1) {
				out.printLine(add(ID));
			} else {
				remove(ID);
			}
		}
	}

	int n;
	HashMap<Integer, Integer> leftID, rightID, size, startIndex, goodSize;
	TreeSet<ComparablePair<ComparablePair<Integer, Integer>, Integer>> set;
	int left;
	int length;
	int right;

	int add(int ID) {
		if (set.isEmpty()) {
			left = ID;
			startIndex.put(ID, 0);
			size.put(ID, n);
			goodSize.put(ID, -(size.get(ID) - 2));
			set.add(new ComparablePair<>(new ComparablePair<>(goodSize.get(ID),startIndex.get(ID)), ID));
		} else {
			int newID = set.first().second;

			int pos;

			int len;

			if (!rightID.containsKey(newID)) {
				pos = size.get(newID) - 1;
			} else {
				len = size.get(newID) - 1;
				pos = (len + 1) / 2;
			}

			len = -set.first().first.first;

			if (left == -1 && len <= length - 1) {
				left = ID;
				startIndex.put(ID, 0);
				size.put(ID, length);
				rightID.put(ID, right);
				leftID.put(right, ID);
				int good = (size.get(ID) - 2) / 2;
				if (size.get(ID) == 1) good = -(1 << 20);
//				set.add(new ComparablePair<>(new ComparablePair<>(-good, startIndex.get(ID)), ID));
				goodSize.put(ID, -good);
				set.add(new ComparablePair<>(new ComparablePair<>(goodSize.get(ID), startIndex.get(ID)), ID));

			} else {
				set.remove(set.first());

				if (rightID.containsKey(newID)) { // has right
					leftID.put(rightID.get(newID), ID);
					rightID.put(ID, rightID.get(newID));
				}
				rightID.put(newID, ID);
				leftID.put(ID, newID);



				startIndex.put(ID, startIndex.get(newID) + pos);
				size.put(ID, startIndex.get(newID) + size.get(newID) - startIndex.get(ID));
				size.put(newID, size.get(newID) - size.get(ID));

				int good = (size.get(ID) - 2) / 2;
				if (!rightID.containsKey(ID))
					good = size.get(ID) - 2;
				if (size.get(ID) == 1) good = -(1 << 20);

//				set.add(new ComparablePair<>(new ComparablePair<>(-good, startIndex.get(ID)), ID));
				goodSize.put(ID, -good);
				set.add(new ComparablePair<>(new ComparablePair<>(goodSize.get(ID), startIndex.get(ID)), ID));
//				set.add(new ComparablePair<>(new ComparablePair<>(-((size.get(newID) - 2) / 2), startIndex.get(newID)), newID));
				goodSize.put(newID, -((size.get(newID) - 2) / 2));
				if (size.get(newID) == 1) goodSize.put(newID, (1 << 20));
				set.add(new ComparablePair<>(new ComparablePair<>(goodSize.get(newID), startIndex.get(newID)), newID));
			}
		}

		return startIndex.get(ID) + 1;
	}

	void remove(int ID) {
		if (set.size() == 1) {
			set.clear();
			leftID.clear();
			rightID.clear();
			size.clear();
			startIndex.clear();
			goodSize.clear();
		} else {
			set.remove(new ComparablePair<>(new ComparablePair<>(goodSize.get(ID), startIndex.get(ID)), ID));
//			if (rightID.containsKey(ID))
//				set.remove(new ComparablePair<>(new ComparablePair<>(goodSize.get(rightID.get(ID)), startIndex.get(rightID.get(ID))), rightID.get(ID)));
			if (leftID.containsKey(ID))
				set.remove(new ComparablePair<>(new ComparablePair<>(goodSize.get(leftID.get(ID)), startIndex.get(leftID.get(ID))), leftID.get(ID)));

			if (!leftID.containsKey(ID)) {
				if (left != -1) {
					left = -1;
					length = size.get(ID);
					right = rightID.get(ID);
				} else {
					length += size.get(ID);
					right = rightID.get(ID);
				}
				leftID.remove(rightID.get(ID));

			} else if(!rightID.containsKey(ID)) {
				rightID.remove(leftID.get(ID));
				size.put(leftID.get(ID), size.get(leftID.get(ID)) + size.get(ID));
			} else {
				leftID.put(rightID.get(ID), leftID.get(ID));
				rightID.put(leftID.get(ID), rightID.get(ID));
				size.put(leftID.get(ID), size.get(leftID.get(ID)) + size.get(ID));
			}

			if (leftID.containsKey(ID)) {
				int newID = leftID.get(ID);
				if (rightID.containsKey(newID))
					goodSize.put(newID, -((size.get(newID) - 2) / 2));
				else goodSize.put(newID, -(size.get(newID) - 2));

				if (size.get(newID) == 1) goodSize.put(newID, (1 << 20));
				set.add(new ComparablePair<>(new ComparablePair<>(goodSize.get(newID), startIndex.get(newID)), newID));
			}


			leftID.remove(ID);
			rightID.remove(ID);
			size.remove(ID);
			startIndex.remove(ID);
			goodSize.remove(ID);
		}
	}
}

class InputReader {
	private boolean finished = false;

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	private int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int peek() {
		if (numChars == -1)
			return -1;
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				return -1;
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long readLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public static boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private String readLine0() {
		StringBuilder buf = new StringBuilder();
		int c = read();
		while (c != '\n' && c != -1) {
			if (c != '\r')
				buf.appendCodePoint(c);
			c = read();
		}
		return buf.toString();
	}

	public String readLine() {
		String s = readLine0();
		while (s.trim().length() == 0)
			s = readLine0();
		return s;
	}

	public String readLine(boolean ignoreEmptyLines) {
		if (ignoreEmptyLines)
			return readLine();
		else
			return readLine0();
	}

	public BigInteger readBigInteger() {
		try {
			return new BigInteger(readString());
		} catch (NumberFormatException e) {
			throw new InputMismatchException();
		}
	}

	public char readCharacter() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		return (char) c;
	}

	public double readDouble() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		double res = 0;
		while (!isSpaceChar(c) && c != '.') {
			if (c == 'e' || c == 'E')
				return res * Math.pow(10, readInt());
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		}
		if (c == '.') {
			c = read();
			double m = 1;
			while (!isSpaceChar(c)) {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				m /= 10;
				res += (c - '0') * m;
				c = read();
			}
		}
		return res * sgn;
	}

	public boolean isExhausted() {
		int value;
		while (isSpaceChar(value = peek()) && value != -1)
			read();
		return value == -1;
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object... objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object... objects) {
		print(objects);
		writer.println();
	}

	public void printFormat(String format, Object... objects) {
		writer.printf(format, objects);
	}


	public void print(char[] objects) {
		writer.print(objects);
	}

	public void printLine(char[] objects) {
		writer.println(objects);
	}

	public void printLine(char[][] objects) {
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
	}


	public void print(int[] objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(int[] objects) {
		print(objects);
		writer.println();
	}

	public void printLine(int[][] objects) {
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
	}


	public void print(long[] objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(long[] objects) {
		print(objects);
		writer.println();
	}

	public void printLine(long[][] objects) {
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
	}


	public void print(double[] objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(double[] objects) {
		print(objects);
		writer.println();
	}

	public void printLine(double[][] objects) {
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
	}


	public void print(byte[] objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(byte[] objects) {
		print(objects);
		writer.println();
	}

	public void printLine(byte[][] objects) {
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
	}


	public void print(boolean[] objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(boolean[] objects) {
		print(objects);
		writer.println();
	}

	public void printLine(boolean[][] objects) {
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
	}


	public void close() {
		writer.close();
	}

	public void flush() {
		writer.flush();
	}
}

class DebugWriter {
	private final OutputWriter writer;

	public DebugWriter(OutputWriter writer) {
		this.writer = writer;
	}

	private void printDebugMessage() {
		writer.print("debug:\t");
	}


	public void printLine(Object... objects) {
		flush();
		printDebugMessage();
		writer.printLine(objects);
		flush();
	}

	public void printFormat(String format, Object... objects) {
		flush();
		printDebugMessage();
		writer.printFormat(format, objects);
		flush();
	}


	public void printLine(char[] objects) {
		flush();
		printDebugMessage();
		writer.printLine(objects);
		flush();
	}

	public void printLine(char[][] objects) {
		flush();
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
		flush();
	}


	public void printLine(double[] objects) {
		flush();
		printDebugMessage();
		writer.printLine(objects);
		flush();
	}

	public void printLine(double[][] objects) {
		flush();
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
		flush();
	}


	public void printLine(int[] objects) {
		flush();
		printDebugMessage();
		writer.printLine(objects);
		flush();
	}

	public void printLine(int[][] objects) {
		flush();
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
		flush();
	}


	public void printLine(long[] objects) {
		flush();
		printDebugMessage();
		writer.printLine(objects);
		flush();
	}

	public void printLine(long[][] objects) {
		flush();
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
		flush();
	}


	public void printLine(byte[] objects) {
		flush();
		printDebugMessage();
		writer.printLine(objects);
		flush();
	}

	public void printLine(byte[][] objects) {
		flush();
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
		flush();
	}


	public void printLine(boolean[] objects) {
		flush();
		printDebugMessage();
		writer.printLine(objects);
		flush();
	}

	public void printLine(boolean[][] objects) {
		flush();
		for (int i = 0; i < objects.length; ++i)
			printLine(objects[i]);
		flush();
	}


	public void flush() {
		writer.flush();
	}

	public void close() {
		writer.close();
	}
}

class ComparablePair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<ComparablePair<U, V>> {
	public U first;
	public V second;

	public ComparablePair(U first, V second) {
		this.first = first;
		this.second = second;
	}

	@Override
	public int compareTo(ComparablePair<U, V> o) {
		int value = first.compareTo(o.first);
		if (value != 0) return value;
		return second.compareTo(o.second);
	}

	@Override
	public int hashCode() {
		int hFirst = first != null ? first.hashCode() : 0;
		int hSecond = second != null ? second.hashCode() : 0;
		return 31 * hFirst + hSecond;
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;

		ComparablePair pair = (ComparablePair) o;

		return (first != null ? first.equals(pair.first) : pair.first == null) &&
				(second != null ? second.equals(pair.second) : pair.second == null);
	}

	@Override
	protected Object clone() throws CloneNotSupportedException {
		return new ComparablePair<U, V>(first, second);
	}

	@Override
	public String toString() {
		return "(" + first + ", " + second + ")";
	}
}