ჰოტელი

დროის ლიმიტი: 3 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2007/08, FEB, GOLD


ძროხები კანადის სასტუმროში დასასვენებლად დასახლებას აპირებენ. სასტუმროს ოთახები განთავსებულია გრძელი კორიდორის ერთ მწკრივში . ოთახების რაოდენობაა N (1 <= N <= 50,000).

სტუმრები სასტუმროში ჯგუფებით D_i (1 <= D_i<= N) შემოდიან და იკავებენ კოროდორში აუცილებლად მომიჯნე, ნომრების მიხედვით უწყვეტ ოთახებს. ადმინისტრატორი ყოველთვის გამოყოფს კორიდორის დასაწყისიდან უახლოეს უწყვეტ r..r+D_i-1 ოთახების ჯგუფს. თუ ასეთი უწყვეტი ჯგუფი არ არის თავისუფალი, მაშინ სტუმრებს თავაზიანი უარით ისტუმრებენ. დასვენების შემდეგ ჯგუფები ტოვებენ სასტუმროს და ათავისუფლებენ ნომრებს X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1).

თქვენი ამოცანაა შეასრულოთ M (1 <= M < 50,000) რაოდენობით შეკვეთა ჯგუფების სასტუმროში განთავსების და სასტუმროდან ამოწერის მიზნით.

 

შემავალი მონაცემების ფორმატი :

* სტრიქონი 1: ორი მთელი N და M

* სტრიქონები 2..M+1: ხაზი i+1 შეიცავს თითო შეკვეთას

(a) 1 და D_i - შეესაბამება განთავსებას.

(b) 2 X_i და D_i - შეესაბამება სასტუმროდან გამოწერას.

 

გამომავალი მონაცემების ფორმატი :

* სტრიქონები 2... ყოველი განთავსების შეკვეთაზე ამობეჭდეთ r- ჯგუფისთვის გამოყოფილი ოთახების საწყისი ნომერი. თუ ეს შეუძლებელია, დაბეჭდეთ 0.

 

 




მაგალითები

შესატანი მონაცემები
10 6 1 3 1 3 1 3 1 3 2 5 5 1 6 დაკოპირება
გამოსატანი მონაცემები
1 4 7 0 5 დაკოპირება