Autonomous Taxi and Snow Management

In this problem, you are given a grid representing a city square. Each cell (unit square) in the grid has a snow depth, which is a nonnegative integer. An autonomous taxi is able to traverse cells with a snow depth up to a certain limit. At the beginning, all cells have snow depth 0. Every hour, the following happens in order:

• Before any operation, the snow depth of every cell in the grid increases by 1.
• Then exactly one operation is performed, which takes one hour. The operations are one of the following:

1. Row Plowing: Given a row index r, all cells in that row have their snow depth reset to 0.
2. Column Plowing: Given a column index c, all cells in that column have their snow depth reset to 0.
3. Taxi Demonstration: You are given:
   • The maximum snow depth X (a nonnegative integer) that the taxi can traverse.
   • A starting cell (r1, c1) and a destination cell (r2, c2).
   The taxi can only travel on cells whose snow depth is at most X. It may move from one cell to an adjacent cell (sharing a common side). The taxi selects a path with the minimum number of steps from the start to the destination if a valid path exists. Otherwise, the demonstration fails.
   
   Formally, let the snow depth at cell (i,j) be denoted by S_{i,j}. Given a chosen X, a valid path (r1, c1) = (i_0,j_0), (i_1,j_1), \ldots, (i_k, j_k) = (r2,c2) satisfies:</p>

   \( \forall 0 \le t \le k,\ S_{i_t,j_t} \le X \) and for every adjacent pair \( (i_t,j_t) \) and \( (i_{t+1},j_{t+1}) \), they share a common edge. If such a path exists, output the minimum number of moves (where a move is one step between adjacent cells). Otherwise, output -1.

   inputFormat

   The first line contains three integers N, M and Q (1 ≤ N, M ≤ 100, 1 ≤ Q ≤ 10⁴), representing the number of rows, columns, and the number of hours (operations) respectively.

   For the next Q lines, each line represents an operation. Each operation is in one of the following formats:

   • For a row plowing operation: 1 r where 1 ≤ r ≤ N.
   • For a column plowing operation: 2 c where 1 ≤ c ≤ M.
   • For a taxi demonstration: 3 X r1 c1 r2 c2 where X (0 ≤ X ≤ 10⁹) is the maximum snow depth the taxi can traverse, and 1 ≤ r1, r2 ≤ N, 1 ≤ c1, c2 ≤ M are the starting and destination cell coordinates respectively.

   Note that at the beginning of each hour, before processing the operation, the snow depth in every cell increases by 1.

   outputFormat

   For every taxi demonstration operation (operation type 3), output the minimum number of moves required for the taxi to go from the starting cell to the destination cell obeying the snow depth constraint. If it is impossible, output -1. Each result should be printed on a new line.

   sample

   3 3 6
   3 1 1 1 3 3
   1 2
   3 2 1 1 3 3
   2 3
   3 1 3 2 3 1
   3 2 1 1 1 1

   4
   -1
   -1
   0

   </p>