[湖北省选模拟 2024] 永恒 / eternity

总有地上的生灵，敢于直面雷霆的威光。

稻妻的地图可以被划分为 $N$ 行 $M$ 列的网格，第 $i$ 行第 $j$ 列的区域用 $(i,j)$ 表示。曾经，每一块区域中都有一位神之眼拥有者，其元素力编号为 $c_{i,j}$（$0 \le c_{i,j} \le 9$）。 雷电将军降下雷霆的威光，收缴了一部分神之眼。神之眼被收缴的区域，被称为**雷电封锁区**，其他区域称为**非雷电封锁区**。由于你反对眼狩令而遭到通缉，你不能进入**雷电封锁区**，也无法离开稻妻地图区域。 你正在积蓄力量，你可以在**相邻的非雷电封锁区**自由移动。假设你现在在 $(i,j)$，你可以移动到 $(i+1,j),(i-1,j),(i,j+1),(i,j-1)$ 四个区域中的任意一个**非雷电封锁区**。在一次移动中，你积蓄的力量为，经过的所有区域的神之眼元素力编号**依次相连**，对 $1\ 145\ 141$ 取模的结果。例如，你经过的区域神之眼元素力编号依次为 $3,1,0,3,3,3,2,1$，那么你积蓄的力量为 $31033321 \bmod 1145141 = 114514$。**请注意，你的一次移动可以经过相同的非雷电封锁区。重复经过相同的非雷电封锁区将重复积蓄力量。** 常道恢宏，鸣神永恒。永恒的愿望终为南柯一梦，变化的趋势岂可阻挡。稻妻会随时间发生变化。在 $1\sim Q$ 秒，每秒发生了一个事件，事件有如下两种： - `1 x y c`：若 $c$ 为 `#`，表示 $(x,y)$ 的神之眼已经**被收缴**，$(x,y)$ 为雷电封锁区；若 $c$ 为数字字符，则表示 $(x,y)$ 的神之眼拥有者重获元素力编号为 $c$ 的神之眼，或其神之眼元素力编号变化为 $c$，$(x,y)$ 为非雷电封锁区。 - `2 sx sy tx ty v`：请判断是否存在由 $(sx,sy)$ 出发，到达 $(tx,ty)$ 的移动方式，使得你积蓄了恰好为 $v$ 的力量。保证 $(sx,sy)$ 与 $(tx,ty)$ 均为非雷电封锁区。 请回答全部事件 2，保证至少有一次事件 2。

输入共 $N+Q+1$ 行。 第一行为四个整数 $N,M,Q,id$，其中 $id$ 表示该测试点编号。 接下来 $N$ 行，每行 $M$ 个字符，描述了稻妻的地图。若第 $i$ 行第 $j$ 个字符为 `#`，则表示 $(i,j)$ 是**雷电封锁区**；若第 $i$ 行第 $j$ 个字符为数字字符，则 $(i,j)$ 为**非雷电封锁区**，该数字字符描述了 $(i,j)$ 神之眼拥有者的神之眼元素力编号。 接下来 $Q$ 行，依照时间顺序描述了每一秒的事件，描述格式如题目描述所示。

输出若干行，对于每一个事件 2 输出一行： - 若存在积蓄力量为 $v$ 的移动方式，输出 `Yes`； - 若不存在积蓄力量为 $v$ 的移动方式，输出 `No`。

5 5 5 0
19999
14519
99949
9999#
999#0
2 1 1 3 4 114514
2 5 1 3 1 99999
2 1 1 5 5 0
2 5 1 1 5 557047
2 3 1 4 4 838871

Yes
Yes
No
Yes
Yes

见选手目录下的 eternity/eternity2.in 与 eternity/eternity2.ans。

该样例符合测试点 9 ∼ 11 的限制。

见选手目录下的 eternity/eternity3.in 与 eternity/eternity3.ans。

### 样例解释 1 **请注意，全部样例输入中 $id$ 均为 $0$。** 对于第一组询问，$(1,1)\to (2,1)\to (2,2)\to (2,3)\to (2,4)\to (3,4)$。 对于第二组询问，$(5,1)\to (5,2)\to (4,2)\to (3,2)\to (3,1)$。 对于第三组询问，有雷电封锁区阻挡，显然无法到达。 对于第四组询问，$(5,1)\to (4,1)\to (3,1)\to (2,1)\to (1,1)\to (1,2)\to (1,3)\to (1,4)\to (1,5)$，权值为 $999119999 \bmod 1145141=557047$。 对于第五组询问，$(3,1)\to (4,1)\to (4,2)\to (4,3)\to (4,4)\to (4,3)\to (4,4)$ ，权值为 $9999999\bmod 1145141=838871$。 ### 子任务 对于所有测试数据，保证 $1 \le n,m \le 500$，$1 \le Q \le 2\times10^5$，$1 \le x, sx, tx \le N$，$1 \le y,sy,ty \le M$，$0 \le v < 1145141$。输入的迷宫仅包含 `#` 和数字字符。 | 测试点编号 | $N,M \le$ | 特殊性质 | | :--: | :--: | :--: | | $1\sim 2$ | $2$ | B | | $3\sim 4$ | $500$ | A | | $5\sim 6$ | $500$ | B,C | | $7\sim 8$ | $500$ | C | | $9\sim 11$ | $500$ | B,D | | $12\sim 13$ | $500$ | D | | $14\sim 17$ | $500$ | B | | $18\sim 20$ | $500$ | 无 | 特殊性质 A：对于每一个询问，不存在合法方案，或存在不超过 $5$ 步的方案。 特殊性质 B：不存在操作 $1$。 特殊性质 C：任何时候所有非雷电封锁区的格子，上面的数字是 $0$。 特殊性质 D：任何时候所有非雷电封锁区的格子，上面的数字相同。