Trong một nhà hát có \(N\) chỗ ngồi, chúng được xếp thành một hàng dài đánh số từ \(1\) đến \(N\) và từ trái qua phải. Ghế số \(1\) gần khán đài nhất và ghế số \(N\) là ghế xa nhất. Khi thấy phía trong nhà hát còn ghế trống thì nhân viên bán vé mới bán vé cho khán giả vào. Ban đầu tất cả các ghế đều trống, khách đầu tiên vào chắc chắn sẽ ngồi ghế trên cùng (ghế số \(1\)). Mỗi khi có khán giả vào thêm, họ luôn chọn chỗ sao cho khoảng cách từ họ đến người gần nhất là xa nhất có thể. Nếu có nhiều chỗ như vậy thì họ chọn ghế có số thứ tự nhỏ nhất.

Trong suốt buổi hòa nhạc, nhân viên bán vé thấy có \(Q\) người ra và vào. Hỏi số ghế mỗi người vào sau là số nào theo cách chọn chỗ như trên.

Dữ liệu vào

• Dòng đầu là hai số \(N,Q\) \((1 \le N \le 10^{18}; 1 \le Q \le 10^5)\)
• \(Q\) dòng tiếp theo mô tả người ra, người vào
• Nếu là \(1\) thì có người vào và cần tìm số ghế mà người đó chọn;
• Nếu là \(2\) \(i\) thì là người thứ \(i\) đi ra khỏi nhà hát.

Dữ liệu ra

Gồm nhiều số tương ứng với số ghế của những người vào sau đã chọn.

Input 1

2 7
1
1
2 1
1
2 2
2 3
1

Output 1

1
2
1
1

Giải thích

Có 2 ghế và 7 lượt vào ra.

• Người \(1\) vào, chọn ghế \(1\)
• Người \(2\) vào, chọn ghế \(2\)
• Người \(1\) ra, ghế \(1\) trống;
• Người \(3\) vào, chọn ghế \(1\);
• Người \(2\) ra, ghế \(2\) trống;
• Người \(3\) ra, ghế \(1\) trống;
• Người \(4\) vào chọn ghế \(1\).