Farmer John's n cows, conveniently numbered 1...n, are all standing in a row (they seem to do so often that it now takes very little prompting from Farmer John to line them up). Each cow has a breed ID: 1 for Holsteins, 2 for Guernseys, and 3 for Jerseys. Farmer John would like your help counting the number of cows of each breed that lie within certain intervals of the ordering.
The first line contains n and q (1≤n,q≤105).
The next n lines contain an integer that is either 1,2 or 3, giving the breed ID of a single cow in the ordering.
The next q lines describe a query in the form of two integers a,b (a≤b).
For each of the q queries (a,b), print a line containing three numbers: the number of cows numbered a,b (a≤b) that are Holsteins (breed 1), Guernseys (breed 2), and Jerseys (breed 3).