أبقار Farmer John وعددها $N$، مرقمة $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