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

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

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

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

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

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

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

შესატანი მონაცემები: პირველი სტრიქონი შეიცავს ორ მთელს N და Q (1≤N≤100000,

1 \leq Q \leq 100, 000

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

გამოსატანი მონაცემები: უპასუხეთ ყველა

Q

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

(a, b)

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