ყუთები და ჭიქები

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

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

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

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

წყარო: COCI, 2008/09, #5


მოცემულია 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 დაკოპირება