Pispirispi finalmente llegó a trabajar, y hay una gran cantidad de tareas que le esperan. A Pispirispi se le da una matriz que consta de n filas y m columnas y q tareas. Cada tarea consiste en intercambiar dos submatrices de la matriz dada.

Para cada tarea Pispirispi conoce seis enteros a_i, b_i, c_i, d_i, h_i, w_i, donde a_i es el índice de la fila donde se encuentra la esquina superior izquierda del primer rectángulo, b_i es el índice de su columna, c_i es El índice de la fila de la esquina superior izquierda del segundo rectángulo, d_i es el índice de su columna, h_i es la altura del rectángulo y w_i es su ancho.

Está garantizado que dos rectángulos en una consulta no se solapan y no se tocan, es decir, ninguna celda pertenece a ambos rectángulos, y no hay dos celdas pertenecientes a rectángulos diferentes que compartan un lado. Sin embargo, los rectángulos se les permite compartir un ángulo.

Pispirispi quiere saber cómo se verá la matriz después de realizar todas las tareas.

Input

La primera línea de la entrada contiene tres números enteros n, m y q (2 ≤ n, m ≤ 1000, 1 ≤ q ≤ 10.000) - el número de filas y columnas en la matriz, y el número de tareas que Pispirispi tiene que realizar.

A continuación, siguen n líneas que contienen m enteros v_{i, j} (1 ≤ v_{i, j} ≤ 109) cada uno - valores iniciales de las celdas de la matriz.

Cada una de las siguientes líneas q contiene seis enteros a_i, b_i, c_i, d_i, h_i, w_i, (1 ≤  a_i, c_i,  h_i  ≤ n,  1 ≤  b_i,  d_i, w_i ≤ m).

Output

Imprima n líneas que contengan m enteros cada una - la matriz resultante.

Example

Input:
4 4 2
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
1 1 3 3 2 2
3 1 1 3 2 2
Output:
4 4 3 3
4 4 3 3
2 2 1 1
2 2 1 1
Input:
4 2 1
1 1
1 1
2 2
2 2
1 1 4 1 1 2
Output:
2 2
1 1
2 2
1 1