矩阵交换行hard

由于easy版本只有一个查询，所以同学们偷懒没有实打实地写矩阵行交换

题目描述

给定一个 $N \times M$ 的矩阵(数学上，一个 $N \times M$ 的矩阵是一个由 $N$ 行 $M$ 列元素排列成的矩形阵列)。

有Q次交换操作：第$i$次操作需要将第 $x$ 行和第 $y$ 行交换

所有操作结束后，输出交换后的结果。

输入格式

第一行，输入两个整数$N,M$ $(1\leq N,M \leq 100)$ 表示矩阵有$N$行，$M$列

接下来$N$行，每行输入$M$个整数，保证不超过$int$类型

接下来一个整数$Q$ $(1\leq Q \leq 1000)$

接下来$Q$行，每行输入两个整数$x,y$ $(1\leq x,y \leq N)$

输出格式

输出Q次交换之后的矩阵，矩阵的每一行元素占一行，元素之间以一个空格分开。

样例 #1

样例输入 #1

5 5
1 2 2 1 2
5 6 7 8 3
9 3 0 5 3
7 2 1 4 6
3 0 8 2 4
3
1 2
3 4
3 5

样例输出 #1

5 6 7 8 3
1 2 2 1 2
3 0 8 2 4
9 3 0 5 3
7 2 1 4 6