მოცემულია N ცალი ყუთი ერთ რიგში, გადანომრილი 1_დან N_მდე. K იყოს მაქსიმალური რიცხვი, რომლისთვისაც K*K<=N. ყუთები დაყოფილია K ზომის ჯგუფებად (ბოლო ჯგუფი შესაძლოა უფრო პატარა ზომის იყოს). თითოეულ ჯგუფს აქვს თავისი შესაბამისი ჭიქა. სლავკო ყუთებზე აკეთებს შემდეგნაირ ოპერაციებს: ირჩევს ორ რიცხვს A და S, ყუთებში ნომრებით A, A+1, A+2, … , A+S-1 უნდა ჩაიდოს თითო ასანთის ღერი. თუმცა, თუ ოპერაციის დროს რომელიმე ჯგუფის თითოეულ ყუთში იდება ღერი, სლავკო ამის ნაცვლად ჯგუფის შესაბამის ჭიქაში ჩადებს 1 ღერს. თქვენი ამოცანაა თითოეული M ოპერაციისთვის დაადგინოთ რამდენი ღერის დამატება მოუწევს სლავკოს. 

https://imgur.com/CorkPcy

შესატანი მონაცემები:

პირველ ხაზზე N და M (1 <= N, M <= 100,000). შემდეგი M ცალი სტრიქონიდან თითოეულზე შემოდის S და A (1 <= A <= N, 1 <= A+S-1 <= N).

გამოსატანი მონაცემები:

M ცალ სტრიქონზე უნდა გამოიტანოთ თითო რიცხვი, i_ურ სტრიქონზე - i_ური ოპერაციისთვის საჭირო ასანთის ღერების რაოდენობა. პასუხში უნდა გაითვალისწინოთ წინა ოპერაციებზე იმ ჭიქაში ან ყუთში მოთავსებული ასანთის ღერების რაოდენობა, რომელშიც ასანთის ღერები მოცემული ოპერაციის დროს მოთავსდა. 

მაგალითები

შესატანი მონაცემები
11 3
6 5
3 1
11 1
                  დაკოპირება

გამოსატანი მონაცემები
4
1
6
                  დაკოპირება

შესატანი მონაცემები
16 3
2 2
12 3
6 11
                  დაკოპირება

გამოსატანი მონაცემები
2
7
3
                  დაკოპირება