Background

There are always living beings on the ground who dare to face the might of thunderhead-on.

Problem Description

The map of Inazuma can be divided into a grid with $N$ rows and $M$ columns. The area in row $i$ and column $j$ is denoted as $(i,j)$. In the past, in every area there was a Vision holder, whose elemental power number was $c_{i,j}$ ($0 \le c_{i,j} \le 9$).

The Raiden Shogun brought down the might of thunder and confiscated some Visions. Areas where the Vision has been confiscated are called Thunder Blocked Areas, and the other areas are called Non-Thunder Blocked Areas. Since you opposed the Vision Hunt Decree and are now wanted, you cannot enter Thunder Blocked Areas, and you also cannot leave the Inazuma map.

You are gathering strength, and you can move freely between adjacent Non-Thunder Blocked Areas. Suppose you are currently at $(i,j)$, you may move to any one of the four areas $(i+1,j),(i-1,j),(i,j+1),(i,j-1)$ that is a Non-Thunder Blocked Area. During one movement, the strength you accumulate is defined as follows: concatenate, in order, the elemental power numbers of the Visions in all areas you pass through, and take the result modulo $1\ 145\ 141$. For example, if the elemental power numbers of the areas you pass through in order are $3,1,0,3,3,3,2,1$, then the strength you accumulate is $31033321 \bmod 1145141 = 114514$. Note that one movement may pass through the same Non-Thunder Blocked Area multiple times. Repeatedly passing through the same Non-Thunder Blocked Area will accumulate strength repeatedly.

The path is vast, Narukami is eternal. The wish for eternity will eventually become an empty dream, and the trend of change cannot be stopped. Inazuma will change over time. During seconds $1 \sim Q$, one event happens each second. There are two types of events:

• 1 x y c: If $c$ is #, it means the Vision at $(x,y)$ has been confiscated, and $(x,y)$ becomes a Thunder Blocked Area. If $c$ is a digit character, it means the Vision holder at $(x,y)$ regains a Vision whose elemental power number is $c$, or its elemental power number changes to $c$, and $(x,y)$ becomes a Non-Thunder Blocked Area.

• 2 sx sy tx ty v: Determine whether there exists a movement that starts from $(sx,sy)$ and reaches $(tx,ty)$ such that the strength you accumulate is exactly $v$. It is guaranteed that both $(sx,sy)$ and $(tx,ty)$ are Non-Thunder Blocked Areas.

Answer all type 2 events. It is guaranteed that there is at least one type 2 event.

Input Format

The input contains $N+Q+1$ lines.

The first line contains four integers $N,M,Q,id$, where $id$ denotes the test point number.

The next $N$ lines each contain $M$ characters describing the Inazuma map. If the $j$-th character in the $i$-th line is #, then $(i,j)$ is a Thunder Blocked Area. If it is a digit character, then $(i,j)$ is a Non-Thunder Blocked Area, and this digit character gives the elemental power number of the Vision held at $(i,j)$.

The next $Q$ lines describe the events that happen each second in chronological order, with the format as described above.

Output Format

Output several lines. For each type 2 event, output one line:

• If there exists a movement whose accumulated strength is $v$, output Yes.
• Otherwise, output 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。

Hint

Sample Explanation 1

Note that in all sample inputs, $id$ is $0$.

For the first query: $(1,1)\to (2,1)\to (2,2)\to (2,3)\to (2,4)\to (3,4)$.

For the second query: $(5,1)\to (5,2)\to (4,2)\to (3,2)\to (3,1)$.

For the third query, it is blocked by a Thunder Blocked Area, so it is clearly impossible to reach.

For the fourth query: $(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)$, and the value is $999119999 \bmod 1145141=557047$.

For the fifth query: $(3,1)\to (4,1)\to (4,2)\to (4,3)\to (4,4)\to (4,3)\to (4,4)$, and the value is $9999999\bmod 1145141=838871$.

Subtasks

For all testdata, it is guaranteed that $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$. The input maze contains only # and digit characters.

Special property A: For each query, either no valid solution exists, or there exists a solution of no more than $5$ steps.

Special property B: There is no operation 1.

Special property C: At any time, for all Non-Thunder Blocked Area cells, the digit on the cell is $0$.

Special property D: At any time, for all Non-Thunder Blocked Area cells, the digits on the cells are the same.

Translated by ChatGPT 5