Raiden Lockdown Path Power

In the world of Inazuma, the map is divided into an N×M grid. The cell in the i-th row and j-th column is denoted as \((i,j)\). Initially, every cell \((i,j)\) contains a digit \(c_{i,j}\) (with \(0 \le c_{i,j} \le 9\)) representing the element power of the "Vision" residing there.

After the mighty Raiden Shogun confiscated some Visions, the affected cells become Raiden Lockdown Zones while the others remain as Non-Raiden Zones. As a rebel against the Vision Hunt Decree, you are forbidden from entering any Raiden Lockdown Zone, and you also cannot leave the boundaries of the grid.

You are training to amass power. You can move freely between adjacent non‐lockdown cells (up, down, left, right). When you are in cell \((i,j)\) with digit \(d\) and move into an adjacent non‐lockdown cell with digit \(d'\), the new power is computed by concatenating the digits (in the order the cells are visited) and then taking the resulting number modulo \(1145141\). For example, if you pass through cells whose digits (in order) are \(3,1,0,3,3,3,2,1\) then your power is computed as:

[ 31033321 \bmod 1145141 = 114514, ]

Note that if you pass through the same non‐lockdown cell multiple times, its digit is counted as many times as it appears in your path.

Time flows and the map changes. There are \(Q\) events happening at seconds \(1\) through \(Q\). Each event is one of the following types:

• 1 x y c: Update event. If \(c\) is a '#' character, the cell \((x,y)\) is confiscated (i.e. it becomes a Raiden Lockdown Zone). If \(c\) is a digit character, then the cell \((x,y)\) becomes (or remains) a Non‐Raiden Zone with its Vision digit updated to \(c\).
• 2 sx sy tx ty v: Query event. Given that both the source \((sx,sy)\) and target \((tx,ty)\) cells are guaranteed to be Non‐Raiden Zones, determine whether there exists a path from \((sx,sy)\) to \((tx,ty)\) (moving only through adjacent non‐lockdown cells, and possibly visiting the same cell multiple times) such that the power you accumulate by concatenating the digits along the path (interpreted as a number in base 10 and taken modulo \(1145141\)) is exactly \(v\).

There is at least one query event. Answer all query events.

Note: The concatenation process starts with the digit in the starting cell.

inputFormat

The first line contains three integers \(N\), \(M\), and \(Q\).

The next \(N\) lines each contain a string of length \(M\) representing the initial grid. Each character is a digit (\(0-9\)) indicating the element power of the Vision in that cell.

The following \(Q\) lines each describe an event. Each event is in one of the following formats:

• 1 x y c: Update event. If c is '#' then cell \((x,y)\) becomes a Raiden Lockdown Zone. Otherwise, c is a digit character and cell \((x,y)\) becomes a Non‐Raiden Zone with its digit set to c.
• 2 sx sy tx ty v: Query event. \(sx,sy\) are the coordinates of the source and \(tx,ty\) are the coordinates of the target, and \(v\) (an integer) is the target power value.

All coordinates are 1-indexed. It is guaranteed that for every query event both the source and target cells are Non‐Raiden Zones at the time of the query.

outputFormat

For each query event (type 2), output a single line containing either Yes if such a path exists, or No otherwise.

sample

2 2 3
12
34
2 1 1 1 2 12
1 1 2 #
2 1 1 1 2 12

Yes
No

</p>