სამნაირი ჯიში

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

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

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

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

წყარო: USACO, 2015/16, DEC, SILVER


ფერმერ ჯონის ძროხები, დანომრილი რიცხვებით 1N1…N, დგანან ერთ მწკრივში. ყოველ ძროხას გააჩნია ჯიში : 1 Holsteins, 2 Guernseys, და 3 Jerseys. ჯონს სურს დათვალოს მწკრივის გარვეულ ინტერვალებში ყოველი ჯიშის ძროხების რაოდენობა.

შესატანი მონაცემები: პირველი სტრიქონი შეიცავს ორ მთელს N და Q (1N100000, 1≤Q≤100000) - ძროხების რაოდენობა და შეკითხვების რაოდენობა შესაბამისად. შემდეგი N სტრიქონი შეიცავს რიცხვებს 1, 2, ან 3, ნუმერაციის მიხედვით. შემდეგ Q სტრიქონში განთავსებულია შეკითხვები ორი a,b (ab) რიცხვის სახით, რაც აღწერს ინტერვალებს,  რომლებშიც საჭიროა ძროხების ჯიშების მიხედვით მათი რაოდენობის გათვლა..
 
გამოსატანი მონაცემები: უპასუხეთ ყველა Q შეკითხვას და თითო სტრიქონში გამოიტანეთ შესაბამისი სამეული: რამდენია Holsteins (ჯიში 1), Guernseys (ჯიში 2), და Jerseys (ჯიში 3) ძროხების რაოდენობა.



მაგალითები

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