Necklace Commands

You are given a necklace consisting of $N$ beads arranged in a circle. The positions on the necklace are fixed on a board with position $1$ marked, and then the other positions are labeled $2,3,\dots,N$ in clockwise order. Each bead is painted in one of $c$ colors, numbered from $1$ to $c$.

Your task is to create a software system that supports the following two types of commands:

• C pos color: Change the color of the bead at position pos to the specified color.
• Q l r: Query the segment of beads from position l to r in clockwise order. Note that if l > r, the segment wraps around: it consists of beads from position l to position $N$ followed by beads from position 1 to position r. The answer should be the frequency of each color from $1$ to $c$ in the segment, reported as c space-separated integers.

Input Format: The first line contains two integers $N$ and $c$. The second line contains $N$ integers representing the initial colors of the beads. The third line contains an integer $M$ denoting the number of commands. Each of the next $M$ lines contains a command in one of the two formats described above.

Output Format: For each query command, output one line with c integers corresponding to the counts of colors $1,2,\dots,c$ in the queried segment.

All formulas are written in LaTeX format.

inputFormat

The input begins with a line containing two integers $N$ and $c$ — the number of beads and the number of colors. The next line contains $N$ integers, where the i-th integer is the color of the i-th bead. The third line contains an integer $M$ representing the number of commands. Each of the following $M$ lines contains a command of one of the following two formats:

• C pos color — change the bead at position pos to color color.
• Q l r — query the segment from position l to r in clockwise order.

If l > r in a query, the segment consists of beads from position l to $N$ followed by beads from position 1 to r.

outputFormat

For each query command, output a line containing c space-separated integers. The i-th integer represents the count of beads with color i in the specified segment.

sample

5 3
1 2 3 2 1
4
Q 1 5
C 3 1
Q 4 2
Q 3 3

2 2 1
2 2 0
1 0 0