მაიმუნი და ვაშლის ხეები

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

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

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

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

წყარო: IZHO, 2012


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

კრისის ყოველი მოსვლისათვის თქვენმა პროგრამამ უნდა გამოთვალოს რამდენ ხეზეა დამწიფებული ვაშლები ამორჩეულ ინტერვალში. დასაწყისისათვის ვაშლები არცერთ ხეზე არ არის დამწიფებული.

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

პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი M (1 <= M <=100000) - მოვლენების რაოდენობა მომდევნო M სტრიქონიდან თითოეულში ხდება მოვლენის აღწერა სამი მთელი რიცხვით Di, Xi, Yi, (1<= Di<=2, Xi <= Yi). თუ პირველი რიცხვი Di=1, ხდება მოვლენა“კრისის მოსვლა“, ხოლო თუ Di=2, ხდება მოვლენა „ვაშლების დამწიფება ხეზე“. დანარჩენი ორი რიცხვი Xi და Yi აღწერენ მოვლენის ინტერვალს.

ინტერვალის გამოთვლისას დიდ როლს თამაშობს რიცხვი C, რომელიც თავდაპირველად 0–ის ტოლია. ინტერვალი, რომელშიც მოვლენა ხდება, ესაა Xi+C–დან Yi+C–მდე თავად ამ რიცხვების ჩათვლით. გარანტირებულია, რომ 1 <= Xi+C; Yi+C <= 109. თუ ხდება მოვლენა“ხეზე ვაშლების დამწიფება“, მაშინ რიცხვი C, არ იცვლება,ხოლო თუ ხდება მოვლენა “კრისის მოსვლა“, რიცხვი C–ს ძველი მნიშვნელობა ღებულობს მონაწილეობს ინტერვალის საზღვრების გამოთვლაში,ხოლო შემდეგ მას ენიჭება ამავე ინტერვალში მწიფე ვაშლების მქონე ხეების რაოდენება.

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

კრისის ყოველ მოსვლაზე თითო სტრიქონში ერთი მთელი რიცხვი: ამოცანის პასუხი.




მაგალითები

შესატანი მონაცემები
3 2 5 8 2 7 10 1 1 10 დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება
შესატანი მონაცემები
4 2 2 3 1 1 3 2 2 3 1 -1 3 დაკოპირება
გამოსატანი მონაცემები
2 4 დაკოპირება
შესატანი მონაცემები
6 2 1 7 2 10 12 1 7 11 2 11 13 1 8 10 1 15 17 დაკოპირება
გამოსატანი მონაცემები
3 2 0 დაკოპირება

შენიშვნა

ტესტების 35–სათვის M <= 10 000, 1 <= Xi + C; Yi + C <= 106.

ტესტების 60–სათვის 1 <= Xi + C; Yi + C <= 107.