$N$ коров Farmer John с номерами $1 \ldots N$ стоят в ряд (так часто, что теперь достаточно слегка попросить). Код породы: $1$ — Holsteins, $2$ — Guernseys, $3$ — Jerseys. Помогите считать каждую породу в заданных интервалах ряда.

Входные данные

Первая строка: $N$ и $Q$ ($1 \leq N \leq 100,000$, $1 \leq Q \leq 100,000$).

Следующие $N$ строк: по целому $1$, $2$ или $3$, порода каждой коровы по порядку.

Следующие $Q$ строк: запрос из двух целых $a, b$ ($a \leq b$).

Выходные данные

Для каждого из $Q$ запросов $(a,b)$ выведите три числа: количества коров с номерами $a \ldots b$ пород Holsteins ($1$), Guernseys ($2$), Jerseys ($3$), в этом порядке.

Примеры

Входные данные 1

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

Выходные данные 1

3 2 1
1 0 0
2 0 1

Автор задачи: Nick Wu