Let's declare three integer arrays s[i]~(1 \le i \le 3). The prefix sums for cows of breed $i$ will be stored in the array $s[i]$.

The answer to the query $(a,b)$ is computed as follows:

• The number of cows of breed $1$ is s[1][b] - s[1][a - 1];

• The number of cows of breed $2$ is s[2][b] - s[2][a - 1];

• The number of cows of breed $3$ is s[3][b] - s[3][a - 1];

Example

For the given example, the prefix sum arrays s[i]~(1 \le i \le 3) will be as follows:

Consider the query on the interval $(2,4)$:

• The number of cows of breed $1$ is s[1][4] - s[1][1] = 2 - 0 = 2;

• The number of cows of breed $2$ is s[2][4] - s[2][1] = 1 - 1 = 0;

• The number of cows of breed $3$ is s[3][4] - s[3][1] = 1 - 0 = 1;

Algorithm implementation

Declare an array for storing prefix sums.

#define MAX 100001
int s[4][MAX];

Read the input data.

scanf("%d %d", &n, &q);

Compute the prefix sum arrays.

memset(s, 0, sizeof(s));
for (i = 1; i <= n; i++)
{
  scanf("%d", &x);
  for (j = 1; j <= 3; j++)
    s[j][i] = s[j][i - 1];
  s[x][i]++;
}

Process the $q$ queries sequentially.

for (i = 0; i < q; i++)
{
   scanf("%d %d", &a, &b);
   printf("%d %d %d\n", s[1][b] - s[1][a - 1], s[2][b] - s[2][a - 1], 
                        s[3][b] - s[3][a - 1]);
}

Python implementation

import sys

Read the input data.

n, q = map(int, input().split())

Declare a list for storing prefix sums.

s = [[0] * (n + 1) for _ in range(4)]

Compute the prefix sum arrays.

for i in range(1, n + 1):
  x = int(input())
  for j in range(1, 4):
    s[j][i] = s[j][i - 1]
  s[x][i] += 1

Process the $q$ queries sequentially.

for _ in range(q):
  a, b = map(int, input().split())
  print(s[1][b] - s[1][a - 1], s[2][b] - s[2][a - 1], 
        s[3][b] - s[3][a - 1])