Description

智慧树下智慧果，智慧树下你和我，智慧树前做游戏，欢乐多又多，小朋友们大家好，欢迎来到智慧树乐园，让我们边唱边跳，快乐成长吧!
这段话想必会唤起很多人的童年回忆，ACMer们小时候也是一样每天晚上守在电视机前等待少儿频道的《智慧树》,如今ACMer们仍然对树很痴迷，善于思考的小Z同学想出了一道关于智慧树的题，想要考考大家。
小Z同学把由“0”和“1”组成的字符串分为三类：全“0”串称为A串，全“1”串称为C串，既含“0”又含“1”的串则称为M串。
小Z定义ACM树是一种二叉树[1](不知道二叉树没关系，下面有注释），它的结点类型也包括A结点，C结点和M结点三种。由一个长度为2的n次幂的“01”串S可以构造出一棵ACM树T，递归的构造方法如下：
1) T的根结点为R，其类型与串S的类型相同；
2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2的n次幂的“01”串，请用上述构造方法构造出一棵ACM树，并分别输出它所包含A,C,M节点的数量。
提示：
[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

Format

Input

第一行是一个整数N（0 <= N <= 10）
第二行是一个长度为2的n次幂的“01”串。

Output

输出分四行：
三个整数，分别占三行，分别表示ACM树中A，C，M节点的数量
最后一行输出ACM树的后序遍历[2]

Samples

3
10001011

A:5
C:5
M:5
CAMAAAMCAMCCCMM

Hint