题目描述

豫让探得赵襄子将过汾桥，遂藏身桥下。他屏息凝神，握紧利刃，只待车驾经过时跃起行刺。连日饥寒交迫，仍坚守不退。为了更好地完成目标，他将桥面划分为 $n$ 行 $m$ 列的监视矩阵 $g$，记录着每一处的守备情况。

豫让观察到，守备情况不断地在调整。在 $q$ 次守备调整中，每次调整给出两个整数 $x,y$ ($1 \le x,y \le n$)，需要将第 $x$ 行与第 $y$ 行的守备布置完全互换。具体来说，你需要交换 $g_{x,1}$ 和 $g_{y,1}$、$g_{x,2}$ 和 $g_{y,2}$、$g_{x,3}$ 和 $g_{y,3}$、…、$g_{x,m}$ 和 $g_{y,m}$。

请输出经过所有调整后的最终守备布置。

输入格式

第一行两个整数 $n,m$ ($1 \le n,m \le 10^6, n \times m \le 10^6$)。

接下来 $n$ 行，每行 $m$ 个整数，描述这个整数矩阵 $g$，其中输入第 $i+1$ 第 $j$ 个整数表示 $g_{i,j}$ ($0 \le g_{i,j} \le 1$) 的值，相邻两个整数用一个空格隔开。

接下来一行一个整数 $q$ ($1 \le q \le 10^6$)，表示调整次数。

接下来 $q$ 行，每行两个整数 $x,y$ ($1 \le x,y \le n$)，表示一次调整。

输出格式

总共 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行第 $j$ 个整数表示操作结束后 $g_{i,j}$ 的值，一行相邻两个数字用一个空格隔开。

3 4
1 0 1 0
1 1 1 1
0 0 0 0
2
1 2
2 3

1 1 1 1
0 0 0 0
1 0 1 0