Problem Background

There are always beings on the earth who dare to face the might of the thunder.

Problem Description

The Inazuma map can be divided into an \(N \times M\) grid, where the region at the \(i\)-th row and \(j\)-th column is denoted as \((i,j)\). Once, each region had an owner of an Eye of the Thunder God, whose elemental power was numbered as \(c_{i,j}\) (\(0 \le c_{i,j} \le 9\)).

The Thunder God将军 (Shogun) has confiscated some Eyes of the Thunder God, turning those regions into Thunder Lock Zones, while the other regions are Non-Thunder Lock Zones. As you oppose the Eye Confiscation Decree and are being hunted, you cannot enter Thunder Lock Zones or leave the Inazuma map area.

You are accumulating power and can move freely between adjacent Non-Thunder Lock Zones. Assuming you are at \((i,j)\), you can move to \((i+1,j)\), \((i-1,j)\), \((i,j+1)\), or \((i,j-1)\) if they are Non-Thunder Lock Zones. In one move, the power you accumulate is the result of concatenating the elemental power numbers of all regions passed through, modulo \(1,145,141\). For example, if the elemental power numbers you pass through are \(3,1,0,3,3,3,2,1\), then the power you accumulate is \(31033321 \bmod 1145141 = 114514\). Note that you can pass through the same Non-Thunder Lock Zone multiple times, and each repetition will add to your accumulated power.

The eternal wish of Inazuma is but a dream. The trend of change cannot be stopped. Inazuma changes over time. For \(1 \sim Q\) seconds, each second an event occurs, which can be one of two types:

• 1 x y c: If \(c\) is #, it means the Eye at \((x,y)\) has been confiscated, making \((x,y)\) a Thunder Lock Zone; if \(c\) is a digit, it means the Eye owner at \((x,y)\) has regained or changed their elemental power number to \(c\), making \((x,y)\) a Non-Thunder Lock Zone.

• 2 sx sy tx ty v: Determine if there is a way to move from \((sx,sy)\) to \((tx,ty)\) such that you accumulate exactly \(v\) power. Ensure \((sx,sy)\) and \((tx,ty)\) are Non-Thunder Lock Zones.

Answer all event 2 queries, ensuring there is at least one event 2.

Input Format

The input consists of \(N+Q+1\) lines.

The first line contains four integers \(N, M, Q, id\), where \(id\) is the test point number.

The next \(N\) lines, each containing \(M\) characters, describe the Inazuma map. If the \(i\)-th row and \(j\)-th character is #, it means \((i,j)\) is a Thunder Lock Zone; if it is a digit, \((i,j)\) is a Non-Thunder Lock Zone, and the digit describes the elemental power number of the Eye owner at \((i,j)\).

The next \(Q\) lines describe each second's event in chronological order, following the format described in the problem.

Output Format

Output several lines, one for each event 2:

• If there is a way to accumulate \(v\) power, output Yes;
• If there is no way to accumulate \(v\) power, output No.

Sample Input and Output

Sample Input #1

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

Sample Output #1

Yes
Yes
No
Yes
Yes

Notes/Hints

For all sample inputs, \(id\) is \(0\).

For the first query, the path is \((1,1) \to (2,1) \to (2,2) \to (2,3) \to (2,4) \to (3,4)\).

For the second query, the path is \((5,1) \to (5,2) \to (4,2) \to (3,2) \to (3,1)\).

For the third query, there is a Thunder Lock Zone blocking the way, so it is impossible to reach.

For the fourth query, the path is \((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)\), with a power value of \(999119999 \bmod 1145141 = 557047\).

For the fifth query, the path is \((3,1) \to (4,1) \to (4,2) \to (4,3) \to (4,4) \to (4,3) \to (4,4)\), with a power value of \(9999999 \bmod 1145141 = 838871\).

Subtasks

For all test data, \(1 \le N, M \le 500\), \(1 \le Q \le 2 \times 10^5\), \(1 \le x, sx, tx \le N\), \(1 \le y, sy, ty \le M\), \(0 \le v < 1145141\). The input maze only contains # and digit characters.

Special Condition A: For each query, there is no valid solution or a solution with no more than 5 steps.

Special Condition B: There are no operation 1 events.

Special Condition C: At all times, the numbers on all Non-Thunder Lock Zones are 0.

Special Condition D: At all times, the numbers on all Non-Thunder Lock Zones are the same.

见题面 Input 部分

见题面 Output 部分