Đếm giống bò

Cho dãy $N$ con bò xếp hàng, mỗi con thuộc một trong ba giống: $1$, $2$, hoặc $3$.

Trả lời $Q$ truy vấn, mỗi truy vấn cho hai số $a$ và $b$, hỏi số con bò thuộc mỗi giống trong đoạn từ vị trí $a$ đến $b$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $Q$.
• $N$ dòng tiếp theo: mỗi dòng một số nguyên ($1$, $2$, hoặc $3$) — giống của con bò thứ $i$.
• $Q$ dòng tiếp theo: hai số nguyên $a$ và $b$ ($a\le b$).

Dữ liệu ra

• $Q$ dòng, mỗi dòng ba số nguyên — số bò giống $1$, giống $2$, giống $3$ trong đoạn $[a,b]$.

Ràng buộc

• $1\le N\le 100000$
• $1\le Q\le 100000$

Ví dụ