该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小Z和小K都迷上了自走棋这个游戏，他们设计了一个字符串上的自走棋。

这个字符串 $S$ 长度为 $n$，仅由 $A/B/C$ 三种字符构成。其中有胜负关系：

• A>B
• B>C
• C>A

$A>B$ 表示 $A$ 战胜 $B$，其余类似。

小Z和小K只需要分别挑选自己的起点 $i,j$，然后他们各自的英雄就会以 $S_i,S_j$ 为起点进行回合作战，每个回合两个英雄会依次向后挪一格，如果到了结尾就重新从 $S_0$ 开始循环。

一共会进行 $k$（从0开始）回合， 每个回合小Z获胜就可以得 $k$ 分。如：

1. 第 $0$ 回合是 $S_i$ 与 $S_j$ 作战，如果 $S_i$ 能赢小Z就会得 $0$ 分
2. 第 $1$ 回合是 $S_{i+1}$ 与 $S_{j+1}$ 作战，如果 $S_{i+1}$ 能赢小Z就会得 $1$ 分
3. 第 $2$ 回合是 $S_{i+2}$ 与 $S_{j+2}$ 作战，如果 $S_{i+2}$ 能赢小Z就会得 $2$ 分
4. ...

注意，只有小Z获胜小Z才可得分，如果平局或者小Z输了他也不会扣分。

记 $f(i,j)$ 为小Z小K分别选取的起点为 $i,j$ 时，小Z获得的分数，求出所有情况下的 $f(i,j)$

输入格式

第一行包含一个正整数 $n$，表示字符串 $S$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $S$。字符串仅由字符 A、B 和 C 组成。

输出格式

输出 $n$ 行，每行包含 $n$ 个由空格分隔的整数。

第 $i + 1$ 行的第 $j + 1$ 个整数应为 $f(i,j)$，其中 $0 \le i, j < n$。

输入输出样例

3
ABC

0 3 0
0 0 3
3 0 0

样例 $\tt \#1$说明

当 $(i,j)=(0,1)$ 时，小Z依次选择 A、B、C，小K依次选择 B、C、A。小Z赢得全部三轮，总分为 $0 + 1 + 2 = 3$，因此 $f(0,1) = 3$。

同理，$f(1,2) = f(2,0) = 3$。对于其余六组起始位置，小Z没有赢得任何一轮，因此对应的 $f(i,j)$ 均为 $0$。

数据范围

子任务编号	分数	$n\le$
$1$	$30$	$100$
$2$	$70$	$2000$

对于 $100\%$ 的数据，满足 $1 \le n \le 2000$，字符串 $s$ 的长度为 $n$，且仅由字符 A、B 和 C 组成。