Migrated from Lutece 2258 征程的结束，吉安娜

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

拔出剪枝哀伤的阿尔搜斯,抛弃了圣光，抛弃了所有品质，变成了暴力军团最忠实的奴仆！

阿尔搜斯,已经彻底疯了.吉安娜----阿尔搜斯曾经的女友痛苦的想着,回去找大先知,或许一切还有救

吉安娜是搜索王国的一位法师,她能够在空间传送,可惜的是:由于法力不够强大,吉安娜只能进行一次传送,并且她不知道自己会传送去哪

再传送用过后,吉安娜只能依靠王国的传送水晶来进行移动,传送水晶的传送方式如下

王国是地图一个n*m的01矩阵,其中只有一个传送水晶,其余所有位置都有一个王国的建筑.王国的有些建筑是不能移动的,有些建筑则可以移动,任何一个与传送水晶相邻(上下左右)的建筑都可以和水晶互换坐标

吉安娜想了q个方案,每一次她会假设传送水晶在第ex行,ey列.她传送后出现在sx行,sy列,大先知在tx行,ty列.假设每次坐标交换都需要1s,吉安娜想知道每次她是否能到达大先知那里,如果能,最少需要多少时间

每个方案独立,也就是说,每次方案开始时每个建筑能否移动在一开始给出,并不会随着方案进行改变

吉安娜虽然法力不够强大,但她可以确保自己第一次传送完在可移动的建筑上

Input

第一行有 3个整数，每两个整数之间用一个空格隔开，依次表示n,m,q；(n,m<=30,q<=500)

接下来的 n 行描述一个n*m 的地图，每行有m个整数，每两个整数之间用一个空格隔开，每个整数描述王国中一个建筑的状态，0 表示该位置的建筑是固定的，1 表示该位置的建筑可以移动或者该位置是传送水晶所在位置。

接下来的 q 行，每行包含 6 个整数依次是 $EX_i$,$EY_i$,$SX_i$,$SY_i$,$TX_i$,$TY_i$ ，每两个整数之间用一个空格隔开，表示每次方案传送水晶的位置，吉安娜的初始位置和大先知的位置

Output

共q 行，每行包含 1 个整数，表示每个方案所需要的最少时间，如果某次方案无法完成目标则输出$−1$。

Samples

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

2
-1

Resources

2019 UESTC ACM Training for Search Algorithm and String