$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