Підрахунок породи

Кілька сезонів спекотного літа та холодної зими добряче пошкодили огорожу $n$ корів Фермера Джона, які вишикувалися в ряд і послідовно пронумеровані від $1$ до $n$. Кожна корова належить до однієї з трьох порід: $1$ — Holsteins, $2$ — Guernseys, $3$ — Jerseys. Фермер Джон просить вас підрахувати кількість корів кожної породи в межах заданого інтервалу.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $q(1\le n,q\le 10^5)$.

Наступні $n$ рядків містять по одному цілому числу $1,2$ або $3$ — ідентифікатор породи відповідної корови.

Наступні $q$ рядків описують запити, кожен із яких складається з двох цілих чисел $a,b(a\le b)$.

Вихідні дані

Для кожного із $q$ запитів $(a,b)$ виведіть рядок, що містить три цілі числа — кількість корів кожної породи на інтервалі від $a$ до $b$ включно.

Приклади