$n$ коров Фермера Джона, последовательно пронумерованных от $1 ... n$, выстроены в ряд. Каждая корова имеет ID породы: $1$ --- Holsteins, $2$ --- Guernseys, $3$ --- Jerseys. ФД просит Вас посчитать количество коров каждой породы, внутри некоторого интервала этого порядка. \InputFile Первая строка содержит $n$ и $q~(1 \le n, q \le 10^5)$. Следующие $n$ строк содержат целое число $1, 2$ или $3$ --- ID породы соответствующей коровы. Следующие $q$ строк описывают запрос в виде двух целых чисел $a, b~(a \le b)$. \OutputFile Для каждого из $q$ запросов $(a, b)$, выведите строку, содержащую три целых числа количество коров в интервале $a ... b$, имеющих номера пород $1, 2, 3$.