Grid (color, 3s, 512M)

Bytegrid 是 Byteland 最新潮的游戏。在这个游戏中，玩家在一个 $n\times n$ 的网格上辗转腾挪。

具体地，玩家可以从任意格子出发，一开始属于失能状态。第 $i$ 行第 $j$ 列的格子在时刻 $a_{i,j}$ 会充能，如果当时玩家处于该格子就可以花 $0.1$ 秒转移到任意相邻（四联通）格，并再次变为失能状态。每到达一个格子玩家都会获得一个新的奇遇，因此玩家可能的移动方案数决定了每局游戏的丰富程度。

作为 Bytegrid 的开发者，你计划上线一个新版本，其中网格有一个格子不会被充能（但仍然可以出发或被移动到）。你有 $q$ 种不同的更新计划，每次计划给定了 $i,j$，指定了第 $i$ 行第 $j$ 列的格子不会被充能（相当于将 $a_{i,j}$ 置为 $-\infty$），你希望获取在移除该格后玩家可能的移动方案数对 $998244353$，其中移动方案指的是依次经过的格子序列。每次计划都是在原网格上进行改动，即计划两两独立。

输入格式

第一行一个正整数 $n$，表示网格大小。

接下来 $n$ 行，第 $i$ 行 $n$ 个正整数 $a_{i,1},a_{i,2},\cdots,a_{i,n}$，表示初始第 $i$ 行每个格子的充能时刻。

接下来一行一个正整数 $q$，表示计划的个数。

接下来 $q$ 行，每行三个正整数 $x,y$，表示该次计划使第 $x$ 行第 $y$ 列的格子无法被充能。

输出格式

输出 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 个计划中玩家的移动方案数，对 $998244353$ 取模。

样例输入1

2
1 2
4 4
3
1 1
2 1
2 2

样例输出1

12
16
14

在第一次测试中，一种可能的移动序列为 $(1,2),(2,2),(2,1)$：第一次测试中玩家可以在 $(1,2)$ 出发，在 $2$ 时刻被充能后转移到 $(2,2)$，在 $4$ 时刻被充能后转移到 $(2,1)$。

注意 $(1,2),(2,2),(2,1),(1,1)$ 并不是可能的移动序列：到达 $(2,1)$ 时 $4$ 时刻已经过去，所以玩家无法再在 $(2,1)$ 上被充能。

第一次测试中所有合法的移动序列：$[(1,1)],$ $[(1,2)],$ $[(1,2),(1,1)],$ $[(1,2),(2,2)],$ $[(1,2),(2,2),(1,2)],$ $[(1,2),(2,2),(2,1)],$ $[(2,1)],$ $[(2,1),(1,1)],$ $[(2,1),(1,2)],$ $[(2,2)],$ $[(2,2),(1,2)],$ $[(2,2),(2,1)]$，共 12 个。

样例输入2、样例输出2

见选手文件夹下 ex_grid2.in 和 ex_grid2.ans。

样例输入3、样例输出3

见选手文件夹下 ex_grid3.in 和 ex_grid3.ans。

数据范围

对于所有数据，$2\le n\le 500$，$1\le q\le 10^6$，$1\le a_{i,j}\le 10^9$。

对于 20% 的数据，$n,q \le 40$。

对于 40% 的数据，$n,q \le 200$。

对于 60% 的数据，$q\le 500$。

对于另外 20% 的数据，输入中的所有时刻（$a$）两两不同。