#P18410. Game

Game

Game

一种名为 Boundle 的游戏规则如下:每个回合,玩家向主持人询问一个由五个大写英文字母组成的字符串。主持人心中有一个同样由五个大写英文字母组成的秘密答案,整局游戏中答案保持不变。主持人用一个长为五的字符串回应,每一位为 <、= 或 >,表示秘密答案该位字母相对于询问该位字母的字母表顺序:分别为小于、等于、大于。

姐妹 Yui 和 Ui 准备玩这个游戏。姐姐 Yui 是主持人,妹妹 Ui 是玩家。Ui 有一个含 n 个不同字符串的询问集合;Yui 已经为集合中每个字符串准备了固定的回应。然而,粗心的 Yui 准备的全部回应实际上互相矛盾:保证不存在任何秘密答案能够同时满足这些回应。

每个回合,Ui 从集合中尚未询问过的字符串里等概率随机选择一个,并得到对应的固定回应。Ui 足够聪明,只要目前得到的回应已经不可能同时成立,她便立即发现姐姐没有始终一致的秘密答案,游戏就此停止。

对于每个 i=1,2,…,n,求 Ui 恰好在第 i 回合回应后第一次发现矛盾时,游戏进行方式的数量。不同的进行方式由实际询问的有序字符串序列区分;游戏停止后不再询问,未选择的字符串不组成额外后缀。

特别地,与某些同类游戏不同,即使目前的回应已经把秘密答案缩小为唯一一种可能,游戏仍然继续,直到所有字符串都问过,或回应出现矛盾。保证把全部字符串问完一定会发生矛盾。

输入格式

第一行一个整数 n,1≤n≤100000。

接下来 n 行,每行两个字符串:第一个是 Ui 询问集合中的字符串,第二个是 Yui 准备的固定回应。

所有询问串两两不同,均恰有五个大写英文字母。每个回应恰有五个字符,每个字符均为 <、=、> 之一。回应本身允许使一个询问就不可能成立,例如对字母 Z 回应 >。

保证不存在任何五位大写英文字母串能够同时满足全部 n 个回应。输入只有一组数据。

输出格式

输出一行 n 个整数,第 i 个表示恰在第 i 回合第一次发现矛盾的游戏进行方式数量,对 998244353 取模。

样例 1

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

样例 2

3
BVHUQ ><>><
YJCEQ <<><<
SXXWZ >>==>
1 4 0

样例 3

8
IFSXA >><<=
ZAKDA <>=>=
UZVAA <<<>=
MTACA <>>>=
RJKVA <><<=
IOXOA >=<<=
MRMHA ><<<=
BYFWA ==<>=
0 16 108 396 816 720 0 0

样例 4

8
BRKPR ><=<>
VUCTO <<=<=
PTCDB <<=>>
PHMGV <><><
FGWHD >><>>
SUSFH <<<<>
IOLDD <<<<>
WJPXX <><<<
0 14 120 444 744 360 0 0