\(N\) con bò của Farmer John, được đánh số thuận tiện từ \(1\ldots N\), đang đứng thành một hàng (dường như chúng làm vậy thường xuyên đến mức giờ đây Farmer John chỉ cần nhắc rất ít là chúng đã xếp hàng). Mỗi con bò có một mã giống: 1 đối với Holstein, 2 đối với Guernsey và 3 đối với Jersey. Farmer John muốn bạn giúp đếm số bò thuộc mỗi giống nằm trong một số đoạn nhất định của hàng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\) (\(1\le N\le100\,000\), \(1\le Q\le100\,000\)).

\(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên bằng 1, 2 hoặc 3, cho biết mã giống của một con bò trong hàng.

\(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn dưới dạng hai số nguyên \(a,b\) (\(a\le b\)).

Dữ liệu ra

Với mỗi truy vấn \((a,b)\) trong số \(Q\) truy vấn, in một dòng chứa ba số: số bò được đánh số từ \(a\ldots b\) thuộc giống Holstein (giống 1), Guernsey (giống 2) và Jersey (giống 3).

Ví dụ

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

3 2 1
1 0 0
2 0 1

Nguồn

USACO 2015 December Contest, Silver - Breed Counting: https://usaco.org/index.php?page=viewproblem2&cpid=572

Tác giả: Nick Wu.