Problem: Vasiliy finally got to work, where there is a huge amount of tasks waiting for him. Vasiliy is given a matrix consisting of n rows and m columns and q tasks. Each task is to swap two submatrices of the given matrix.

For each task Vasiliy knows six integers ai, bi, ci, di, hi, wi, where ai is the index of the row where the top-left corner of the first rectangle is located, bi is the index of its column, ci is the index of the row of the top-left corner of the second rectangle, di is the index of its column, hi is the height of the rectangle and wi is its width.

It's guaranteed that two rectangles in one query do not overlap and do not touch, that is, no cell belongs to both rectangles, and no two cells belonging to different rectangles share a side. However, rectangles are allowed to share an angle.

Vasiliy wants to know how the matrix will look like after all tasks are performed.

Input

The first line of the input contains three integers n, m and q (2 ≤ n, m ≤ 1000, 1 ≤ q ≤ 10 000) — the number of rows and columns in matrix, and the number of tasks Vasiliy has to perform.

Then follow n lines containing m integers vi, j (1 ≤ vi, j ≤ 109) each — initial values of the cells of the matrix.

Each of the following q lines contains six integers ai, bi, ci, di, hi, wi (1 ≤ ai, ci, hi ≤ n, 1 ≤ bi, di, wi ≤ m).

Output

Print n lines containing m integers each — the resulting matrix.

Examples

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

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    int[][] idx;
    int[] values;
    int[] rightIdx;
    int[] downIdx;
    IntArrayList row1;
    IntArrayList row2;
    IntArrayList column1;
    IntArrayList column2;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      int n = in.nextInt();
      int m = in.nextInt();
      int q = in.nextInt();
      idx = new int[n + 2][m + 2];
      int idxCnt = 0;
      for (int i = n + 1; i >= 0; --i)
        for (int j = m + 1; j >= 0; --j) {
          idx[i][j] = idxCnt++;
        }
      int n2m2 = (n + 2) * (m + 2);
      values = new int[n2m2];
      rightIdx = new int[n2m2];
      downIdx = new int[n2m2];
      for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
          if (i > 0 && j > 0) {
            values[idx[i][j]] = in.nextInt();
          }
          rightIdx[idx[i][j]] = idx[i][j + 1];
          downIdx[idx[i][j]] = idx[i + 1][j];
        }
      row1 = new IntArrayList(n << 1);
      row2 = new IntArrayList(n << 1);
      column1 = new IntArrayList(m << 1);
      column2 = new IntArrayList(m << 1);
      for (int i = 0; i < q; ++i) {
        int x1 = in.nextInt();
        int y1 = in.nextInt();
        int x2 = in.nextInt();
        int y2 = in.nextInt();
        int h = in.nextInt();
        int w = in.nextInt();
        update(x1, y1, x2, y2, h, w);
      }
      int rowHead = idx[0][0];
      for (int i = 0; i < n; ++i) {
        rowHead = downIdx[rowHead];
        int cell = rowHead;
        for (int j = 0; j < m; ++j) {
          cell = rightIdx[cell];
          out.print(values[cell]);
          out.print(j + 1 == m ? '\n' : ' ');
          //out.printf("%d%c", values[cell], j + 1 == m ? '\n' : ' ');
        }
      }
    }

    private void update(int x1, int y1, int x2, int y2, int h, int w) {
      extract(x1, y1, h, w, row1, column1);
      extract(x2, y2, h, w, row2, column2);
      for (int i = 0; i < row1.size(); ++i) {
        int tmp = rightIdx[row1.get(i)];
        rightIdx[row1.get(i)] = rightIdx[row2.get(i)];
        rightIdx[row2.get(i)] = tmp;
      }
      for (int i = 0; i < column1.size(); ++i) {
        int tmp = downIdx[column1.get(i)];
        downIdx[column1.get(i)] = downIdx[column2.get(i)];
        downIdx[column2.get(i)] = tmp;
      }
    }

    private void extract(int x, int y, int h, int w, IntArrayList row, IntArrayList column) {
      row.clear();
      column.clear();
      int corner = goRight(goDown(idx[0][0], x - 1), y - 1), pnt;
      // down, right
      pnt = corner;
      for (int i = 0; i < h; ++i) {
        pnt = downIdx[pnt];
        row.add(pnt);
      }
      for (int i = 0; i < w; ++i) {
        pnt = rightIdx[pnt];
        column.add(pnt);
      }
      // right, down
      pnt = corner;
      for (int i = 0; i < w; ++i) {
        pnt = rightIdx[pnt];
        column.add(pnt);
      }
      for (int i = 0; i < h; ++i) {
        pnt = downIdx[pnt];
        row.add(pnt);
      }
    }

    int goRight(int idx, int cnt) {
      for (int i = 0; i < cnt; ++i) {
        idx = rightIdx[idx];
      }
      return idx;
    }

    int goDown(int idx, int cnt) {
      for (int i = 0; i < cnt; ++i) {
        idx = downIdx[idx];
      }
      return idx;
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPostion;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPostion = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPostion >= numberOfChars) {
        currentPostion = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPostion++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' '
          || c == '\n'
          || c == '\r'
          || c == '\t'
          || c < 0;
    }

  }

  static interface IntCollection {
  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void close() {
      writer.close();
    }

  }

  static class IntArrayList implements IntCollection {
    private int[] values;
    private int close;

    public IntArrayList(int capacity) {
      values = new int[Integer.highestOneBit(capacity) << 1];
    }


    public void clear() {
      close = 0;
    }


    public int size() {
      return close;
    }


    public void add(int v) {
      ensureCapacity(size() + 1);
      values[close++] = v;
    }

    public int get(int idx) {
      if (idx >= close) throw new ArrayIndexOutOfBoundsException();
      return values[idx];
    }

    protected void ensureCapacity(int capacity) {
      if (capacity < values.length) return;
      int[] newValues = new int[Integer.highestOneBit(capacity) << 1];
      System.arraycopy(values, 0, newValues, 0, values.length);
      close = size();
      values = newValues;
    }

  }
}