题目描述

给定一张 $n$ 个点的无向图 $G$。下面我们考虑的序列都是值在 $[1,n]$ 内的正整数序列。

对于两个长度相同的序列 $a,b$，认为它们等价，当且仅当 $a$ 能通过进行若干次以下操作变成 $b$：

• 选择一个 $1\le i<|a|$，满足 $a_i,a_{i+1}$ 两个结点在图中有直接连边，然后交换 $a_i,a_{i+1}$。

称两个序列 $a,b$ 是可交换的，当且仅当 $ab$ 与 $ba$ 等价。这里 $ab$ 表示将 $b$ 直接拼接到 $a$ 后面得到的序列。

现在给定一个长度为 $m$ 的序列 $a$，你需要求出所有的序列 $b$，满足以下三个条件：

• $a,b$ 可交换
• 不存在两个序列 $c,d$，使得 $b$ 和 $cd$ 等价，且 $c,d$ 均和 $a$ 可交换。
• 不存在一个序列 $b'$，使得 $b'$ 和 $b$ 等价，且 $b'$ 的字典序小于 $b$。

可以证明在本题的约束下，这样的序列个数不超过 $n$ 个。

对于序列 $b$，定义其哈希值 $H(b)=\big(\sum_{i=1}^{|b|}(n+1)^{i-1}b_i\big)\bmod 998244353$。输出所有合法序列的哈希值。

输入格式

从 equivalence.in 中读入数据。

第一行一个正整数 $n$。

接下来 $n-1$ 行，第 $i$ 行有 $n-i$ 个数，每个数是 0 或者 1，第 $j$ 个数表示图中是否存在边 $(i,i+j)$。

接下来一行一个正整数 $m$。

接下来一行 $m$ 个正整数 $a_1,\cdots,a_m$ 表示给出的序列。保证 $1\le a_i\le n$。

输出格式

输出到 equivalence.in 中。

假设共有 $k$ 个序列符合条件，它们按照字典序排序后分别为 $b^{(1)},b^{(2)},\cdots,b^{(k)}$（注意直接排序序列而非排序哈希值），你需要输出 $k$ 行，分别表示 $H(b^{(1)}),H(b^{(2)}),\cdots,H(b^{(k)})$。

样例 $1$ 输入

3
1 1
0
5
2 1 3 2 3

样例 $1$ 输出

1
14

样例 $1$ 解释

合法的序列 $b$ 分别是：$(1),(2,3)$。

样例 $2,3,4$

见下发文件。

测试点约束

对于所有数据，$1\le n\le 200,1\le m\le 3\times 10^5$。

すろーりーないと (feat. 初音ミク)