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 javax.swing.text.Segment;
import java.io.*;
import java.util.*;

public class CodeForces  {
    static boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    public class Segment implements Comparable<Segment> {
        public int st;
        public int e;

        public boolean equals(Object o)
        {
            if (!(o instanceof Segment))
                return false;
            Segment seg = (Segment)o;
            return this.st == seg.st && this.e == seg.e;
        }

        public int compareTo(Segment b) {
            Segment a = this;
            int L1 = Math.abs(a.e - a.st) / 2;
            int L2 = Math.abs(b.e - b.st) / 2;
            if (L1 == L2) {
                if (a.st > b.st)
                    return -1;
                else if (a.st < b.st)
                    return 1;
                else if (a.e > b.e)
                    return -1;
                else if (a.e < b.e)
                    return 1;
                return 0;
            }
            if (L1 < L2)
                return -1;
            return 1;
        }
    }

    public class SegComparator implements Comparator<Segment> {
        @Override
        public int compare(Segment a, Segment b) {
            int L1 = Math.abs(a.e - a.st) / 2;
            int L2 = Math.abs(b.e - b.st) / 2;
            if (L1 == L2) {
                if (a.st > b.st)
                    return -1;
                else if (a.st < b.st)
                    return 1;
                return 0;
            }
            if (L1 < L2)
                return -1;
            return 1;
        }
    }

    void runCase(int caseNum) throws IOException {
        int n = nextInt();
        int m = nextInt();
        int cars = 0;
        Map<Integer, Integer> position = new HashMap<Integer, Integer>();
        //SortedSet<Segment> que= new TreeSet<Segment>(new SegComparator());
        SortedSet<Segment> que= new TreeSet<Segment>();
        SortedMap<Integer, Integer> pos = new TreeMap<Integer, Integer>();
        Segment[] start = new Segment[n];
        Segment[] end = new Segment[n];
        int onlycar = 0;
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < m ; ++i) {
            int td = nextInt();
            int c = nextInt();
            int p = 0;
            if (n == 399 && i == 22545) {
//                out.println("last: " + que.last().st + " " + que.last().e);
//                int cc = 0;
//                Iterator<Segment> iterator = que.iterator();
//                while (iterator.hasNext()) {
//                    Segment seg = iterator.next();
//                    if (188 < ++cc)
//                        out.println("Start: " + seg.st + " end: " + seg.e);
//                }
//                out.println("seg: " + que.size());
                Segment seg1 = null, seg2 = null;
                for (int tt = 38; tt >= 0; --tt) {
                    if (start[tt] != null) {
                        //out.println("39 : " + tt + " start: " + start[tt].st + " end: " + start[tt].e);
                        seg1 = start[tt];
                        break;
                    }
                }
                //que.add(seg1);
//                for (int tt = 38; tt < n; ++tt) {
//                    if (end[tt] != null) {
//                        out.println("39 : " + tt + " start: " + end[tt].st + " end: " + end[tt].e);
//                        break;
//                    }
//                }
//
//                for (int tt = 51; tt >= 0; --tt) {
//                    if (start[tt] != null) {
//                        out.println("51 : " + tt + " start: " + start[tt].st + " end: " + start[tt].e);
//                        seg2 = start[tt];
//                        break;
//                    }
//                }
//                for (int tt = 51; tt < n; ++tt) {
//                    if (end[tt] != null) {
//                        out.println("51 : " + tt + " start: " + end[tt].st + " end: " + end[tt].e);
//                        break;
//                    }
//                }
//                out.println("contains: " + que.contains(seg1));
//                out.println("compare: " + seg1.compareTo(seg2));
//                out.println("td: " + td);
            }
            if (td == 1) {
                //in
                if (cars == 0) {
                    p = 0;
                    onlycar = p;
                } else if (cars == 1) {
                    if (Math.abs(n - 1 - onlycar) > Math.abs(onlycar))
                        p = n - 1;
                    else
                        p = 0;
                    Segment seg = new Segment();
                    seg.st = Math.min(p, onlycar);
                    seg.e = Math.max(p, onlycar);
                    start[seg.st] = seg;
                    end[seg.e] = seg;
                    que.add(seg);
                } else {
                    Segment cur = que.last();
                    p = (cur.st + cur.e) / 2;
//                    if (n == 399 && i == 22545)
//                        out.println("p: " + p);
                    int len = p - cur.st;
                    if (pos.firstKey() >= len) {
                        p = 0;
                        len = pos.firstKey();
                    }
                    if (n - 1 - pos.lastKey() > len) {
                        p = n - 1;
                        len = n - 1 - pos.lastKey();
                    }
                    if (p == 0 || p == n - 1) {
                        Segment sega = new Segment();
                        if (p == 0) {
                            sega.st = p;
                            sega.e = pos.firstKey();
                        } else {
                            sega.st = pos.lastKey();
                            sega.e = n - 1;
                        }
                        start[sega.st] = sega;
                        end[sega.e] = sega;
                        que.add(sega);
                    } else {
                        que.remove(cur);
                        start[cur.st] = null;
                        end[cur.e] = null;
                        p = (cur.st + cur.e) / 2;
                        Segment seg1 = new Segment();
                        Segment seg2 = new Segment();
                        seg1.st = cur.st;
                        seg1.e = p;
                        seg2.st = p;
                        seg2.e = cur.e;
                        que.add(seg1);
                        que.add(seg2);
                        start[seg1.st] = seg1;
                        start[seg2.st] = seg2;
                        end[seg1.e] = seg1;
                        end[seg2.e] = seg2;
                    }
                }
                position.put(c, p);
//                if (pos.containsKey(p))
//                    pos.put(p, pos.get(p) + 1);
//                else
                    pos.put(p, 1);
                ++cars;
//                if (n == 399 && i == 22545)
//                    out.println("p: " + p);
//                if (n != 399)
                //if (n != 399 || i < 22544 )
                    out.println(p + 1);
//                else
//                    out.println("hehe");
            } else {
                p = position.get(c);
//                if (pos.get(p) <= 1)
                    pos.remove(p);
//                else
//                    pos.put(p, pos.get(p) - 1);
                if (start[p]!= null && end[p] != null) {
                    que.remove(start[p]);
                    que.remove(end[p]);
                    Segment seg = new Segment();
                    seg.st = end[p].st;
                    seg.e = start[p].e;
                    start[seg.st] = seg;
                    end[seg.e] = seg;
                    que.add(seg);
                    start[p] = null;
                    end[p] = null;
                }
                if (start[p] != null) {
                    que.remove(start[p]);
                    start[p] = null;
                }
                if (end[p] != null) {
                    que.remove(end[p]);
                    end[p] = null;
                }
                --cars;
                if (cars == 1)
                    onlycar = pos.firstKey();
            }
        }
    }


    public static void main(String[] args) throws IOException {
        if (ONLINE_JUDGE){
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }else{
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
        new CodeForces().runIt();
        out.flush();
        out.close();
        return;
    }

    static BufferedReader in;
    private StringTokenizer st;
    static PrintWriter out;

    String next() throws IOException {
        while (!st.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            st = new StringTokenizer(line, " ");
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }


    void runIt() throws IOException {
        st = new StringTokenizer("");

//        int N = nextInt();
//        for (int i = 0; i < N; i++) {
//            runCase(i + 1);
//        }
        runCase(0);

        out.flush();
    }

}