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.*;
import java.util.*;

public class E {
	InputStream is;

	int __t__ = 1;
	int __f__ = 0;
	int __FILE_DEBUG_FLAG__ = __f__;
	String __DEBUG_FILE_NAME__ = "src/E2";

	FastScanner in;
	PrintWriter out;

	class Elem {
		int r, c;
		int val;
		Elem up, down;
		Elem left, right;
		
		Elem(int r, int c, int val) {
			this.r = r;
			this.c = c;
			this.val = val;
			up = down = null;
			left = right = null;
		}

		public Elem get(int a, int b) {
			Elem cur = this;
			for (int i = 0; i < a; i++) 
				cur = cur.down;
			for (int j = 0; j < b; j++) 
				cur = cur.right;
			return cur;
		}
		
		public String showAnswer(int n, int m) {
			StringBuilder res = new StringBuilder();
			Elem vert = this;
			for (int i = 0; i < n; i++) {
				Elem horr = vert;
				for (int j = 0; j < m; j++) {
					res.append(horr.val + " ");
					horr = horr.right;
				}
				res.append("\n");
				vert = vert.down;
			}
			return res.toString();
		}
		
		public String toString() {
			return "(" + r + ", " + c + ", " + val + ")";
		}
	}
	
	public void solve() {
		int n = in.nextInt(), m = in.nextInt();
		int Q = in.nextInt();

		Elem[][] es = new Elem[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				es[i][j] = new Elem(i, j, in.nextInt());
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				es[i][j].left  = es[i][(j-1+m)%m];
				es[i][j].right = es[i][(j+1)%m];
				es[i][j].up    = es[(i-1+n)%n][j];
				es[i][j].down  = es[(i+1)%n][j];
			}
		}
		
		Elem leftUp = es[0][0];
		for (int q = 0; q < Q; q++) {
			int a = in.nextInt() - 1, b = in.nextInt() - 1;
			int c = in.nextInt() - 1, d = in.nextInt() - 1;
			int h = in.nextInt(), w = in.nextInt();
			
			Elem cur1 = leftUp.get(a, b);
			Elem cur2 = leftUp.get(c, d);
			
			if (cur1 == leftUp) 
				leftUp = cur2;
			else if (cur2 == leftUp)
				leftUp = cur1;
			
			// For debug
			Elem start1 = cur1, start2 = cur2;
			
			// Update left side
			for (int i = 0; i < h; i++) {
				cur1.left.right = cur2;
				cur2.left.right = cur1;
				Elem tmp = cur1.left;
				cur1.left = cur2.left;
				cur2.left = tmp;
				
				if (i != h - 1) {
					cur1 = cur1.down;
					cur2 = cur2.down;
				}
			}
			
			// Update down side
			for (int j = 0; j < w; j++) {
				cur1.down.up = cur2;
				cur2.down.up = cur1;
				Elem tmp = cur1.down;
				cur1.down = cur2.down;
				cur2.down = tmp;
				
				if (j != w - 1) {
					cur1 = cur1.right;
					cur2 = cur2.right;
				}
			}
			
			// Update right side
			for (int i = 0; i < h; i++) {
				cur1.right.left = cur2;
				cur2.right.left = cur1;
				Elem tmp = cur1.right;
				cur1.right = cur2.right;
				cur2.right = tmp;
				
				if (i != h - 1) {
					cur1 = cur1.up;
					cur2 = cur2.up;
				}
			}
			
			// Update up side
			for (int j = 0; j < w; j++) {
				cur1.up.down = cur2;
				cur2.up.down = cur1;
				Elem tmp = cur1.up;
				cur1.up = cur2.up;
				cur2.up = tmp;
				
				if (j != w - 1) {
					cur1 = cur1.left;
					cur2 = cur2.left;
				}
			}
			
			assert start1 == cur1 && start2 == cur2;
		}
		System.out.print(leftUp.showAnswer(n, m));
	}

	public void run() {
		if (__FILE_DEBUG_FLAG__ == __t__) {
			try {
				is = new FileInputStream(__DEBUG_FILE_NAME__);
			} catch (FileNotFoundException e) {
				// TODO 自動生成された catch ブロック
				e.printStackTrace();
			}
			System.out.println("FILE_INPUT!");
		} else {
			is = System.in;
		}
		in = new FastScanner(is);
		out = new PrintWriter(System.out);

		solve();
	}

	public static void main(String[] args) {
		new E().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			return nextIntArray(n, 0);
		}

		int[] nextIntArray(int n, int margin) {
			int[] array = new int[n + margin];
			for (int i = 0; i < n; i++)
				array[i + margin] = nextInt();

			return array;
		}

		int[][] nextIntMap(int n, int m) {
			int[][] map = new int[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextIntArray(m);
			}
			return map;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			return nextLongArray(n, 0);
		}

		long[] nextLongArray(int n, int margin) {
			long[] array = new long[n + margin];
			for (int i = 0; i < n; i++)
				array[i + margin] = nextLong();

			return array;
		}

		long[][] nextLongMap(int n, int m) {
			long[][] map = new long[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextLongArray(m);
			}
			return map;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			return nextDoubleArray(n, 0);
		}

		double[] nextDoubleArray(int n, int margin) {
			double[] array = new double[n + margin];
			for (int i = 0; i < n; i++)
				array[i + margin] = nextDouble();

			return array;
		}

		double[][] nextDoubleMap(int n, int m) {
			double[][] map = new double[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextDoubleArray(m);
			}
			return map;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}