我们的世界已被能够变形并绑架人类、窃取其身份的外星人入侵。你是致力于检测并逮捕他们的特别行动小组的一名调查员。因此，你获得了特殊的工具来检测外星人并将其与真正的人类区分开来。你当前的任务是前往一座怀疑被入侵的城市，秘密检查那里的每一个人，以确定谁是外星人，谁不是，并将这一切报告给总部。这样总部就可以出其不意地向该城市派遣部队，一次性逮捕所有外星人。

外星人察觉到了像你这样的调查员的工作，并且正在监控所有的无线电频道以检测此类报告的传输，从而防范任何报复行动。因此，人们做出了多次加密报告的尝试，而最新的方法使用的是多项式。

你必须访问的城市有 $N$ 名市民，每名市民都由一个介于 $2$ 到 $2N$ 之间的独特偶数来标识。你想找到一个多项式 $P$，使得对于每位市民 $i$，如果市民 $i$ 是人类，则 $P(i) > 0$；否则 $P(i) < 0$。该多项式将被传输给总部。

为了尽量减少传输带宽，该多项式有一些额外的要求：

• 每个根和系数都必须是整数。
• 其最高次项的系数必须为 $1$ 或 $-1$。
• 其次数必须尽可能低。

对于每位市民，你都知道他们是否是人类。给定这些信息，你必须找到一个满足上述约束的多项式。

输入格式

输入仅包含一行，其中有一个长度为 $N$（$1 \le N \le 10^4$）的字符串 $S$，其中 $N$ 是城市的总人口。对于 $i = 1, 2, \dots, N$，$S$ 的第 $i$ 个字符要么是大写字母 H，要么是大写字母 A，分别表示市民 $2i$ 是人类还是外星人。

输出格式

第一行必须包含一个整数 $D$，表示满足上述约束的多项式的次数。

第二行必须包含 $D + 1$ 个整数，表示该多项式的系数，按对应项的次数降序排列。

保证存在至少一个解，使得每个系数的绝对值都小于 $2^{63}$。

样例

输入样例 1

HHH

输出样例 1

0
1

输入样例 2

AHHA

输出样例 2

2
-1 10 -21

输入样例 3

AHHHAH

输出样例 3

3
1 -23 159 -297