说明

chongba是个可怜的单身狗，他也渴望能像Zookkk和langa一样，有着一个爱着自己的活泼可爱的小公主。这天，温柔可爱的小公主ccdxc（滑稽）决定召开一场比武大会，将要嫁给最后的胜者。chongba听到这则消息，迫不及待的准备前往大会，暗暗下定决心一定要把小公主娶到手。消息也传到了一些江湖败类的耳朵里，他们决定一起去拦路打劫那些前往大会的人,不会直接去比武大会和参赛者的家里（因为打不过）。chongba从(1,1)点出发，ccdxc则在(N,N)(2 <= N <= 100)点举行比武大会。

输入格式

第一行输入一个数N,代表一个N * N (2 <= N <= 100)的方格

之后输入一个N * N (2 <= N <= 100)方格，其中1代表无法通行的道路，0代表可通行，接下来输入一个数m(0 <= m <= 20)，代表有m伙江湖败类，

然后接下来的m行每行两个数字x，y (1 <= x, y <= N)代表其埋伏的地点。chongba每走一个方格都要耗费1个小时，而且因为chongba的功法很特殊，所以在行走时，他不能走出方格外面。请你为他找出最佳路径，让他快点赶到美丽的小公主身边。

输出格式

如果存在路径，则第一行输出到达比武大会的最短时间T，之后T + 1行输出chongba应该走的最佳路径（chongba家和比武地点都要输出，每个位置坐标占一行）， 如果不存在能到达的路径则输出-1。数据保证若存在路径，则只有一条最短的路径。

样例

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

6
1 1
2 1
3 1
3 2
3 3
4 3
4 4