sohyunzzq   1년 전

문제

Farmer John의 N마리 소들이 편리하게 1번부터 N번까지 번호가 매겨진 채 줄을 서 있다 (이제는 Farmer John이 시키지 않아도 스스로 줄을 설 정도다). 각 소는 품종 ID를 가지고 있다: 1은 Holsteins, 2는 Guernseys, 3은 Jerseys를 의미한다. Farmer John은 특정 구간에 있는 각 품종의 소 수를 세는 것을 도와달라고 한다.


입력

첫 번째 줄에는 N과 Q가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)

다음 N개의 줄에는 각각 1, 2, 또는 3 중 하나의 정수가 주어진다. 이는 각 소의 품종 ID이다.

다음 Q개의 줄에는 두 정수 a, b가 주어지며 (a ≤ b), 이는 질의의 범위를 나타낸다.


출력

각 Q개의 질의 (a, b)에 대해, 다음 세 개의 수를 출력한다:

  • 번호가 a번부터 b번까지인 소들 중 Holsteins(품종 1)의 수
  • Guernseys(품종 2)의 수
  • Jerseys(품종 3)의 수

댓글을 작성하려면 로그인해야 합니다.