题目背景

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

题目描述

稻妻的地图可以被划分为 $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$。输入的迷宫仅包含 # 和数字字符。

特殊性质 A：对于每一个询问，不存在合法方案，或存在不超过 $5$ 步的方案。

特殊性质 B：不存在操作 $1$。

特殊性质 C：任何时候所有非雷电封锁区的格子，上面的数字是 $0$。

特殊性质 D：任何时候所有非雷电封锁区的格子，上面的数字相同。