CF1197F.Coloring Game

Alice and Bob want to play a game. They have $n$ colored paper strips; the $i$-th strip is divided into $a_i$ cells numbered from $1$ to $a_i$. Each cell can have one of $3$ colors.

In the beginning of the game, Alice and Bob put $n$ chips, the $i$-th chip is put in the $a_i$-th cell of the $i$-th strip. Then they take turns, Alice is first. Each player during their turn has to choose one chip and move it $1$, $2$ or $3$ cells backwards (i. e. if the current cell is $x$, then the chip can be moved to the cell $x - 1$, $x - 2$ or $x - 3$). There are two restrictions: the chip cannot leave the borders of the strip (for example, if the current cell is $3$, then you can't move the chip $3$ cells backwards); and some moves may be prohibited because of color of the current cell (a matrix $f$ with size $3 \times 3$ is given, where $f_{i, j} = 1$ if it is possible to move the chip $j$ cells backwards from the cell which has color $i$, or $f_{i, j} = 0$ if such move is prohibited). The player who cannot make a move loses the game.

Initially some cells may be uncolored. Bob can color all uncolored cells as he wants (but he cannot leave any cell uncolored). Let's call a coloring good if Bob can win the game no matter how Alice acts, if the cells are colored according to this coloring. Two colorings are different if at least one cell is colored in different colors in these two colorings.

Bob wants you to calculate the number of good colorings. Can you do it for him?

Since the answer can be really large, you have to print it modulo $998244353$.

Alice 和 Bob 想玩一个游戏。他们有 $n$ 条彩色纸带；第 $i$ 条纸带被划分为 $a_i$ 个格子，编号从 $1$ 到 $a_i$。每个格子可以是 $3$ 种颜色之一。

游戏开始时，Alice 和 Bob 将 $n$ 枚棋子放置在纸带上：第 $i$ 枚棋子被放在第 $i$ 条纸带的第 $a_i$ 个格子中。然后两人轮流行动，Alice 先手。每位玩家在自己的回合中必须选择一枚棋子，并将其向后移动 $1$、$2$ 或 $3$ 个格子（即：若当前格子编号为 $x$，则可将棋子移至编号为 $x - 1$、$x - 2$ 或 $x - 3$ 的格子）。移动需满足两个限制条件：

• 棋子不能移出纸带边界（例如，若当前格子编号为 $3$，则不允许向后移动 $3$ 格）；
• 某些移动可能因当前格子的颜色而被禁止（给定一个大小为 $3 \times 3$ 的矩阵 $f$，其中 $f_{i, j} = 1$ 表示当格子颜色为 $i$ 时，允许向后移动 $j$ 格；$f_{i, j} = 0$ 表示该移动被禁止）。

无法进行任何合法移动的玩家输掉游戏。

初始时，部分格子可能未着色。Bob 可以任意为所有未着色的格子染色（但不能留下任何格子未着色）。我们称一种染色方案为好染色，当且仅当：若按该方案对所有格子染色，则无论 Alice 如何行动，Bob 均能获胜。若两种染色方案中至少有一个格子的颜色不同，则认为它们是不同的染色方案。

Bob 希望你计算好染色方案的总数。你能帮他完成吗？

由于答案可能非常大，请对 $998244353$ 取模后输出。

The first line contains one integer $n$ — the number of paper strips ($1 \le n \le 1000$).

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the number of cells in the $i$-th strip.

The third line contains one integer $m$ ($1 \le m \le 1000$) — the number of cells that are already colored.

Then $m$ lines follow, each describing an already colored cell. The $i$-th of these lines contains three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i \le n$, $1 \le y_i \le a_{x_i}$, $1 \le c_i \le 3$) denoting that the cell $y_i$ in the strip $x_i$ has color $c_i$. It is guaranteed that if $i \ne j$, then either $x_i \ne x_j$ or $y_i \ne y_j$ (or both).

Then $3$ lines follow, $i$-th line containing $3$ numbers $f_{i, 1}$, $f_{i, 2}$, $f_{i, 3}$ ($0 \le f_{i, j} \le 1$). If $f_{i, j} = 1$, then it is possible to move the chip $j$ cells backwards from the cell having color $i$; if $f_{i, j} = 0$, then such move is impossible.

第一行包含一个整数 $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$，则允许从颜色为 $i$ 的格子向后（即朝纸条起始方向）移动 $j$ 个格子；若 $f_{i, j} = 0$，则不允许进行该移动。

Print one integer: the number of good colorings, taken modulo $998244353$.

输出一个整数：良好染色方案的数量，对 $998244353$ 取模。