Under construction

Still being built. Things may change

Breed Counting

Interview

Time limit2sMemory limit512 MB

Summary
Given the breed of each cow in a row, report the count of each of the three breeds inside every query interval.
Level

Easy3 of 10

Topics
Prefix sum, Array
Solved
No attempts yet

Problem

Farmer John's NN cows, numbered 11 through NN, stand in a row. Each cow carries a breed ID: 1 for Holsteins, 2 for Guernseys, and 3 for Jerseys. Given an interval of the row, count how many cows of each breed stand inside it.

Input

The first line contains NN and QQ (1≤N≤100,0001 \le N \le 100{,}000, 1≤Q≤100,0001 \le Q \le 100{,}000).

Each of the next NN lines contains an integer that is 1, 2, or 3. The number on line ii is the breed ID of the ii-th cow in the row.

Each of the next QQ lines contains two integers aa and bb describing one query (1≤a≤b≤N1 \le a \le b \le N).

Output

For each query (a,b)(a, b), print three integers on one line, separated by spaces: the number of Holsteins (breed 1), Guernseys (breed 2), and Jerseys (breed 3) among cows aa through bb, in that order.

Examples5

  1. Example 1

    Input
    6 3
2
1
1
3
2
1
1 6
3 3
2 4
    Expected output
    3 2 1
1 0 0
2 0 1

  2. Example 2

    Input
    1 1
1
1 1
    Expected output
    1 0 0

  3. Example 3

    Input
    5 4
2
2
2
2
2
1 5
1 1
5 5
2 4
    Expected output
    0 5 0
0 1 0
0 1 0
0 3 0

  4. Example 4

    Input
    3 4
3
1
2
1 1
2 2
3 3
1 3
    Expected output
    0 0 1
1 0 0
0 1 0
1 1 1

  5. Example 5

    Input
    7 3
1
2
1
2
1
1
2
1 7
2 6
4 4
    Expected output
    4 3 0
3 2 0
0 1 0