ნათურების გადართვა

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

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

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

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

წყარო: USACO, 2008/09, NOV, BRONZE


ფერმერ ჯონს სურს გონებამახვილი ძროხები ჰყავდეს, ამიტომ ცდილობს, რომ ინტელექტუალური თამაშებით გაართოს ისინი. ერთ-ერთ ასეთ თამაშს წარმოადგენს ნათურათა გრძელი მწკრივი ბოსელში. 1-დან  N-მდე (2<=N<=500) გადანომრილი თითოეული ძროხის თავზე განლაგებულია ფერადი ნათურა.

თავიდან ყველა ნათურა გამორთულია. ძროხებს აქვთ  N ცალი ჩამრთველი ნათურების სამართავად. i-ურ ჩამრთველზე ზემოქმედებისას i-ური ნათურა აინთება, თუ იგი მანამდე გამორთული იყო და პირიქით, ჩაქრება, თუ მანამდე ჩართული იყო.

ძროხები კითხულობენ და თანმიმდევრობით ასრულებენ M (1<=M<=2,000) ცალ ბრძანებას, რომელთაგან თითოეული აღნიშნულია 0-ით ან 1-ით(0 <= operation <= 1). პირველი ოპერაცია (აღნიშნულია 0-ით) შეიცავს ორ მთელ რიცხვს: S_i და E_i (1<=S_i<=E_i<= N).  ისინი განსაზღვრავენ საწყის და საბოლოო ჩამრთველებს, რომლებზეც უნდა მოხდეს ზემოქმედება.

მეორე ოპერაცია (აღნიშნულია 1-ით) ასევე შეიცავს ორ მთელ რიცხვს: S_i და E_i (1<=S_i<=E_i<= N) და წარმოადგენს შეკითხვას, თუ რამდენი ნათურაა ანთებული მოცემულ დიაპაზონში.

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

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი:  N და M. მომდევნო M სტრიქონიდან თითოეულში სამ-სამი მთელი რიცხვი: operation, S_i, და E_i.

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




მაგალითები

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

შენიშვნა

შეტანის განმარტება: გვაქვს 4 ნათურა და 5 ქმედება.

              ნათურები

            1 2 3 4

  ქმედება:   O O O O   O = off  * = on

  0 1 2 ->  * * O O  აინთო 1 და 2

  0 2 4 ->  * O * *     2..4 დიაპაზონში მდგომარეობები შეიცვალა

  1 2 3 ->  1        2..3 დიაპაზონში ანთებულია 1 ნათურა

  0 2 4 ->  * * O O  კვლავ შეიცვალა მდგომარეობები 2..4 დიაპაზონში

  1 1 4 ->  2        1..4 დიაპაზონში ანთებულია 2 ნათურა