有一个名为 Boundle 的新游戏，规则如下：在每一轮中，玩家向主持人说出一个由 5 个大写英文字母组成的字符串。然后，主持人应回复一个由 <、=、> 组成的长度为 5 的字符串，表示该位置的字符与主持人心中答案字符串的字母顺序关系。答案字符串在整个游戏过程中保持不变，且同样由 5 个大写英文字母组成。

两姐妹 Yui 和 Ui 正在玩 Boundle。姐姐 Yui 担任主持人，妹妹 Ui 担任玩家。Ui 有一个包含 $n$ 个字符串的集合，她将用这些字符串进行询问。对于 Ui 集合中的每一个字符串，Yui 都已经设定了一个固定的回复。然而，这里有一个转折：由于 Yui 很粗心，题目保证实际上不存在一个字符串能匹配她所有的固定回复。

每一轮，Ui 从她尚未选择的集合中随机且均匀地选择一个字符串，并收到该字符串对应的固定回复。对于从 $1$ 到 $n$ 的每一个 $i$，请计算如果 Ui 在第 $i$ 轮之后意识到姐姐 Yui 给出的回复不一致时，游戏可能进行的路径数量。Ui 很聪明，所以当回复无法自圆其说时，她会立即看出 Yui 心中并没有一个真正的答案字符串。

注意，题目保证如果 Ui 完成了集合中所有的字符串，她得到的结果将是不一致的。

此外，由于某些神秘的原因，与原版游戏不同，即使回复已经将可能的答案字符串缩小到只有一种可能性，游戏仍会继续，直到集合中的所有字符串都被选中，或者回复变得不一致。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

随后有 $n$ 行，每行包含两个字符串。第一个字符串属于 Ui 的字符串集合，第二个字符串表示 Yui 对其的回复。

Ui 集合中的所有字符串都是不同的，且由 5 个大写英文字母组成。Yui 的回复是长度为 5 的字符串，仅包含字符 <、= 和 >。

题目保证不存在一个字符串能匹配 Yui 的所有回复。

输出格式

输出一行，包含 $n$ 个整数，其中第 $i$ 个整数表示如果 Ui 在第 $i$ 轮之后意识到 Yui 在撒谎，游戏可能进行的路径数量。

所有数字请对 $998\,244\,353$ 取模。

样例

输入 1

2
FAKER >>>>>
CHOVY =====

输出 1

0 2

输入 2

3
BVHUQ ><>><
YJCEQ <<><<
SXXWZ >>==>

输出 2

1 4 0

输入 3

8
IFSXA >><<=
ZAKDA <>=>=
UZVAA <<<>=
MTACA <>>>=
RJKVA <><<=
IOXOA >=<<=
MRMHA ><<<=
BYFWA ==<>=

输出 3

0 16 108 396 816 720 0 0

输入 4

8
BRKPR ><=<>
VUCTO <<=<=
PTCDB <<=>>
PHMGV <><><
FGWHD >><>>
SUSFH <<<<>
IOLDD <<<<>
WJPXX <><<<

输出 4

0 14 120 444 744 360 0 0