Alice 和 Bob 想玩一个游戏。他们有$$$n$$$彩色纸条;第 $$$i$$$ 条带被分为 $$$a_i$$$ 单元,编号从 $$$1$$$ 到 $$$a_i$$$。每个单元格可以有 $$$3$$$ 颜色之一。
游戏开始时,Alice 和 Bob 投入了 $$$n$$$ 筹码,第 $$$i$$$ 个筹码被放入第 $$$i$$$ 个条带的第 $$$a_i$$$ 个单元格中。然后他们轮流,爱丽丝是第一个。每个玩家在回合中必须选择一个筹码并将其向后移动 $$$1$$$、$$$2$$$ 或 $$$3$$$ 单元格(即,如果当前单元格是 $$$x$$$,则筹码可以移动到 $$$x - 1$$$、$$$x - 2$$$ 或 $$$x - 3$$$ 单元格)。有两个限制:芯片不能离开条带的边界(例如,如果当前单元格是$$$3$$$,则不能向后移动芯片$$$3$$$单元格);并且由于当前单元格的颜色,某些移动可能会被禁止(给出一个大小为 $$$3 \times 3$$$ 的矩阵 $$$f$$$,其中 $$$f_{i, j} = 1$$$ 如果可以将筹码 $$$j$$$ 单元格从具有颜色 $$$i$$$ 的单元格向后移动,或者 $$$f_{i, j} = 0$$$ 如果禁止这种移动)。无法采取行动的玩家输掉游戏。
最初,某些单元格可能是无色的。鲍勃可以根据需要为所有未着色的单元格着色(但他不能让任何单元格不着色)。如果无论 Alice 的行为如何,Bob 都能赢得游戏,如果单元格根据此着色进行着色,我们就称着色为好。如果在这两种着色中至少一个细胞被着色为不同的颜色,则两种着色是不同的。
Bob 希望您计算出良好着色的数量。你能为他做吗?
由于答案可能非常大,因此您必须以 $$$998244353$$$ 为模来打印它。
输入
第一行包含一个整数 $$$n$$$ — 纸条的数量 ($$$1 \le n \le 1000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 条带中的单元格数量。
第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 1000$$$) — 已经着色的单元格数量。
接下来是 $$$m$$$ 行,每行描述一个已经着色的单元格。这些行的第 $$$i$$$ 包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$c_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le a_{x_i}$$$, $$$1 \le c_i \le 3$$$) 表示单元格$$$x_i$$$ 条带中的 $$$y_i$$$ 具有颜色 $$$c_i$$$。保证如果 $$$i \ne j$$$,则 $$$x_i \ne x_j$$$ 或 $$$y_i \ne y_j$$$ (或两者)。
然后是 $$$3$$$ 行,第 $$$i$$$ 行包含 $$$3$$$ 数字 $$$f_{i, 1}$$$, $$$f_{i, 2}$$$, $$$f_{i, 3}$$$ ($$$0 \le f_{i, j} \le 1$$$)。如果 $$$f_{i, j} = 1$$$,则可以将筹码 $$$j$$$ 单元从具有颜色 $$$i$$$ 的单元向后移动;如果$$$f_{i, j} = 0$$$,那么这样的移动是不可能的。
输出
打印一个整数:良好着色的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
3 3 4 5 2 1 1 1 2 2 2 1 1 1 1 0 0 0 1 1
输出 #1
14346
输入 #2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出 #2
1
输入 #3
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出 #3
9