你玩过“Tap the Frog”吗？这是一个包含许多小游戏的合集，在游戏中你需要帮助一只青蛙完成日常任务。今天，我们要讨论的是第二个小游戏，名为“Jump the Frog”。

游戏可以看作是湖面上的一条长条形网格，每个格子要么包含一片荷叶，要么只是水面。在长条的最左侧格子里有一片荷叶，青蛙正坐在上面。游戏界面有 $k$ 个按钮：“向右跳一格”、“向右跳两格”、……、“向右跳 $k$ 格”。为简化起见，与原版游戏不同，我们假设青蛙只能跳到荷叶上；此外，如果青蛙右侧剩余的格子数 $r < k$，则你不能按下“向右跳 $i$ 格”的按钮（其中 $i > r$）。

你想要为这个游戏创建一个关卡。你已经拥有了一些模板，每个模板都可以表示为一个由字符“~”和“O”组成的字符串：ASCII 码为 126 的字符“~”代表没有荷叶的格子，而 ASCII 码为 79 的拉丁字母“O”代表有荷叶的格子。接下来，你创建了几个新模板：在一次操作中，你选取两个模板 $s_i$ 和 $s_j$（可以是两个不同的模板，也可以是同一个），将它们拼接起来，并将得到的字符串 $s_i s_j$ 添加到模板集合中。

对于每个模板，请找出完成该关卡的方法数，即通过按下一些按钮，以某种顺序从最左侧的格子跳到最右侧的格子，且过程中不能经过没有荷叶的格子。如果两种方法按下的按钮次数不同，或者次数相同但在某一步 $i$ 所按下的按钮不同，则视为两种不同的方法。由于这些计数可能非常大，请输出它们对 $998\,244\,353$ 取模的结果。假设如果最左侧或最右侧的格子（或两者）没有荷叶，则方法数为零，即使长条的长度为一也是如此。

输入格式

第一行包含三个整数 $n, k$ 和 $a$：现有模板的数量、青蛙的最大跳跃长度，以及你将要添加的模板数量（$1 \le n, a \le 10^5$；$1 \le k \le 20$）。

接下来的 $n$ 行包含字符串 $s_1, s_2, \dots, s_n$：现有模板的描述（$|s_1| + \dots + |s_n| \le 10^5$）。所有字符串 $s_i$ 均非空，且仅由字符“~”和“O”组成。

接下来的 $a$ 行描述了如何构建模板 $n+1, \dots, n+a$。在第 $i$ 行中，有两个整数 $l_i$ 和 $r_i$，表示第 $n+i$ 个模板是由第 $l_i$ 个和第 $r_i$ 个模板拼接而成的。形式上，$s_{n+i} = s_{l_i} s_{r_i}$（$1 \le l_i, r_i < n+i$）。

输出格式

输出 $n+a$ 个整数 $A'_1, A'_2, \dots, A'_{n+a}$。每个整数 $A'_i$ 必须在 $-2^{63}$ 到 $2^{63} - 1$ 的范围内，且必须满足 $A'_i \equiv A_i \pmod{998\,244\,353}$，其中 $A_i$ 是选择模板 $s_i$ 时从最左侧格子跳到最右侧格子的方法数（即 $A_i - A'_i$ 必须能被 $998\,244\,353$ 整除）。

样例

样例输入 1

4 3 6
O
~
OOO~~
~OOO
4 1
1 4
3 1
3 2
8 1
7 7

样例输出 1

1 0 0 0 0 3 2 0 0 8