\(N\) коров Фермера Джона, последовательно пронумерованных от \(1 \ldots N\),
выстроены в ряд. Каждая корова имеет ID породы: 1 - Holsteins, 2 - Guernseys,
3 - Jerseys. ФД просит Вас посчитать количество коров каждой породы, внутри
некоторого интервала этого порядка.
ФОРМАТ ВВОДА (файл bcount.in):
Первая строка ввода содержит
\(N\) и
\(Q\) (
\(1 \leq N \leq 100,000\),
\(1 \leq Q \leq 100,000\)).
Следующие \(N\) строк содержат целое число 1,2, или 3 - ID породы
соответствующей коровы.
Следующиеt \(Q\) строк описывают запрос в виде двух целых чисел
\(a, b\) (\(a \leq b\)).
ФОРМАТ ВЫВОДА (файл bcount.out):
Для каждого из \(Q\) запросов \((a,b)\), выведите строку, содержащую три
целых числа количество коров в интервале \(a \ldots b\), имеющих номера пород
1,2,3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
2
1
1
3
2
1
1 6
3 3
2 4
|
3 2 1
1 0 0
2 0 1
|