You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

Farmer John的奶牛们组成了若干个奶牛旅行团来到成都旅行，他们很喜欢逛街，想住在春熙路旁边的Amazing Hotel，Amazing Hotel一共有n（1<=n<=50000）个房间排成一排，编号从1到n。

对于一个旅行团的奶牛，他们当然是同时入住酒店，但是根据他们各自的行程安排不同，这些奶牛并不一定是同时离开这家酒店。

这天，有m（1<=m<50000）头奶牛来办理入住或退房手续，他们排着长队，你只需要按顺序办理即可。

若是登记入住，这头奶牛会帮它所在旅行团的奶牛都办理入住。假设这头奶牛所在旅行团牛的数量为y，那么这个旅行团会要求入住连续的y间房间，即旅行团要求入住的房间是[x,x+y-1]的一段连续区间，若有多个x满足要求，则要求x最小。

若是退房，这头奶牛会告诉你它要帮哪些奶牛退房，它要退的房间是一段连续的区间，起始编号为x，一共退y间房，即区间[x,x+y-1]。

【输入】

第一行包含两个正整数n,m。

接下来包含m行，每行第一个数为op，

若op=1，代表办理入住，接下来会输入第二个数y代表旅行团人数。

若op=2，代表办理退房，接下来会输入两个数x，y代表所退起始编号为x，一共退y间房。数据确保退房的区间都是入住了奶牛的。

【输出】

对每一个办理入住的旅行团，输出一个数，代表入住房间的起始编号，若无法满足这个旅行团的要求，输出0。

【输入样例】

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

【输出样例】

1
4
7
0
5

【样例说明】

第1个入住请求入住房间[1,3]，起始编号为1；

第2个入住请求入住房间为[4,6]，起始编号为4；

第3个入住请求入住房间为[7,9]，起始编号为7；

第4个入住请求无法满足请求；

第5个退房请求退的房间是[5,9]；

第6个入住请求入住房间是[5,10]，起始编号为5。