You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

2S/512M

题目描述

给定一个长度为 $n$ 的字符串 $s$，其下标从 $0$ 开始，且每个字符均为 A、B 或 C。

这三种字符之间存在如下克制关系：

• A 战胜 B
• B 战胜 C
• C 战胜 A

两名玩家将进行 $n$ 轮对战，轮次编号依次为 $0, 1, \dots, n - 1$。

对于一组给定的起始位置 $(i, j)$（其中 $0 \le i, j < n$），在第 $k$ 轮（$0 \le k < n$）对战中：

• 第一名玩家选择字符：$s_{(i + k)\bmod n}$
• 第二名玩家选择字符：$s_{(j + k)\bmod n}$

每轮得分规则如下：

• 若第一名玩家选择的字符战胜第二名玩家选择的字符，则第一名玩家赢得该轮，并获得 $k$ 分。
• 否则（两名玩家选择相同字符，或第二名玩家的字符战胜第一名玩家的字符），第一名玩家在该轮获得 $0$ 分。

定义 $W(i, j)$ 为第一名玩家在上述 $n$ 轮对战中获得的总得分（即赢得的所有轮次编号 $k$ 的累加和）。如果第一名玩家没有赢得任何一轮，则总积分为 $0$。

请计算所有满足 $0 \le i, j < n$ 的 $W(i, j)$。

格式

输入格式

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

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

输出格式

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

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

样例

样例输入 #1

3
ABC

样例输出 #1

0 3 0
0 0 3
3 0 0

样例解释 #1

当 $(i,j)=(0,1)$ 时，第一名玩家依次选择 A、B、C，第二名玩家依次选择 B、C、A。第一名玩家赢得全部三轮，总分为 $0 + 1 + 2 = 3$，因此 $W(0,1) = 3$。

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

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

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