페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3946

종류 개수 2s 512MB

문제

Farmer John의 소는 총 N마리이고, 편리하게도 1번부터 N번까지 번호가 매겨져 있다. 모든 소들은 일렬로 서 있으며(이제는 Farmer John이 따로 시키지 않아도 줄을 잘 서는 것 같다), 각 소는 품종 ID를 하나씩 가진다. 품종 ID는 다음과 같다.

  • 1: Holstein

  • 2: Guernsey

  • 3: Jersey

Farmer John은 이 줄에서 여러 구간이 주어졌을 때, 각 구간마다 품종별로 몇 마리의 소가 있는지 세는 일을 도와주기를 원한다.


입력

첫 번째 줄에 정수 N과 Q가 주어진다. (1 ≤ N ≤ 100\ 000, 1 ≤ Q ≤ 10\ 0000)

다음 N개의 줄에는 각각 한 마리의 소에 대한 품종 ID가 주어진다. 각 줄에는 1, 2, 3 중 하나의 정수가 주어지며, 줄의 i번째 값은 번호가 i인 소의 품종 ID를 의미한다.

그 다음 Q개의 줄에는 쿼리가 주어진다. 각 쿼리는 두 정수 a, b로 이루어져 있으며, a ≤ b를 만족한다. 이는 번호가 a번부터 b번까지인 소들로 이루어진 구간을 의미한다.


출력

각 쿼리 (a, b)에 대해 한 줄에 세 개의 정수를 출력한다.

  • 번호 a…b 사이에 있는 Holstein(품종 1) 소의 수

  • 번호 a…b 사이에 있는 Guernsey(품종 2) 소의 수

  • 번호 a…b 사이에 있는 Jersey(품종 3) 소의 수

을 순서대로 공백으로 구분하여 출력한다.


예제 

6 3
2
1
1
3
2
1
1 6
3 3
2 4
3 2 1
1 0 0
2 0 1


출처

USACO 2015 December Silver
로그인해야 코드를 작성할 수 있어요.