ფეიერვერკი

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

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

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

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

წყარო: USACO, 2006/07, MAR, BRONZE


დამოუკიდებლობის დღის აღსანიშნავად ფერმერ ჯონს სურს ბესი ფეიერვერკს დაესწროს. რადგან ბესის გაუჭირდება სრულად უყუროს მთელს შოუს, ფჯ-ის სურს გაიგოს წარმოდგენის რა ნაწილს ნახავს ბესი. რაკეტების გამშვები მოწყობილობები (ქვემეხები) გადანომრილია თანმიმდევრობით 1-დან C-მდე (1<= C <= 100). i-ური ქვემეხიდან ფეიერვერკის რაკეტებს უშვებენ ყოველ T_i (1<= T_i <= N) წამში (ამ ამოცანაში ყველა მონაცემი მთელ რიცხვს წარმოადგენს). წარმოდგენის გახსნისას ყველა ქვემეხიდან გაისვრიან დროის 0 მომენტში. ილუმინაცია (ნათება) რაკეტის გაშვების შემდეგ ჩანს მხოლოდ ერთი წამის განმავლობაში - ეს წამი რაკეტის გაშვების წამია. ბესი ესწრება შოუს  დროის 1 მომენტიდან N (1 <= N <= 2,000,000) წამის ჩათვლით. დაეხმარეთ ფჯ-ის, გაარკვიოს თუ რამდენჯერ დაინახავს ბესი რაკეტების გაშვებას დროის იმ შუალედში, როცა ის შოუზე იქნება. 

 

შეტანის ფორმატი:

* სტრიქონი 1: ჰარით გაყოფილი ორი მთელი რიცხვი: C და N.

* სტრიქონები 2..C+1: სტრიქონი i+1 შეიცავს ერთ მთელ T_i რიცხვს.

 

განმარტება:

შოუზე ორი ქვემეხია: ერთი ისვრის რაკეტას ყოველ 4 წამში, მეორე - ყოველ 6 წამში. ძროხები იმყოფებიან შოუზე 1 წამიდან მე-20 წამის ჩათვლით. ქვემოთ ნაჩვენებია დიაგრამა, რომელიც ასახავს რაკეტების გაშვებას და ძროხების ყოფნას ფეიერვერკზე.

 

      CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC

2                                   2                                   2 ...

1           1     2     1           1           1     2     1           1 ...

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ ...

0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ...

 

გამოტანის ფორმატი:

* სტრიქონი 1: ერთი მთელი რიცხვი - იმ განსხვავებული წამების რაოდენობა 1..N ინტერვალში, რომელთა განმავლობაში ძროხები ხედავენ ფეიერვერკს.

 




მაგალითები

შესატანი მონაცემები
2 20 4 6 დაკოპირება
გამოსატანი მონაცემები
7 დაკოპირება

შენიშვნა

განმარტება:
რაკეტების გაშვება მოხდება დროის შემდეგ მომენტებში: 4, 6, 8, 12, 16, 18, 20 - სულ 7 
განსხვავებული წამი. შევნიშნოთ, რომ მე-12 წამზე ერთდროულად მომხდარი ორი გასროლა, ითვლება ერთად.