Giới thiệu: Đây là đề thi ICPC lậu

H.32 Programming Lab's N pigs, conveniently numbered 1… N, all stand in a line (they seem to do so often so now need very little prompting from SalAqua to line up. them in line). Each pig has a breed ID: 1 for pink, 2 for white and 3 for black. SalAqua would like your help counting the number of pigs of each breed that lie within certain intervals of the ordering.

Input

The first line of input contains N and Q (1≤N≤100,000, 1≤Q≤100,000). The next N lines contain an integer that is either 1, 2, or 3, giving the breed ID of a single pig in the ordering.

The next Q lines describe a query in the form of two integers a,b (a≤b).

Output

For each of the Q queries (a,b), print a line containing three numbers: the number of pigs numbered a…b that are pink (breed 1), white (breed 2), and black (breed 3).

Examples

Input

6 3
2
1
1
3
2
1
1 6
3 3
2 4

Output

3 2 1
1 0 0
2 0 1