[BJOI2019]送别

题目描述

法珞是个怕黑的女孩子。 傍晚了,法珞所参加的学术会议早已散会。黎瑟也下了课过来接法珞回火车站。 但是教学楼里突然断电了,法珞陷入了一片漆黑之中。 好在黎瑟已经到了教学楼的同一层。 然而由于教学楼的结构过于复杂,她们已经记不起教学楼的具体结构了。 黎瑟学校的教学楼每层的结构都非常工整。 形式化地说,教学楼的一层的平面结构可以画在二维平面上以 $(0,0)$ 为左上角顶点,$(n,m)$ 为右下角顶点的子矩形(记为 $(0,0) - (n,m)$ 的矩形)里,这个子矩形的四条边是教学楼的楼体(或者说是四段已知一定存在的墙)。 **请注意,本题中的坐标系和普通的平面直角坐标系不同,$(0,0)$ 是左上角的顶点而 $(n,m)$ 是右下角的顶点。 $(i,j)$ 表示的是第 $i+1$ 行第 $j+1$ 列的顶点而不是横坐标为 $i$ 纵坐标为 $j$ 的顶点。** 每一段墙(无法通过的部分)是一条端点为 $(i,j)$ 和 $(i',j')$ 的线段,记作 $(i,j) - (i',j')$ 的墙,其中 $|i-i'| + |j-j'| =1$ 且 $i,i'$ 是 $[0,n]$ 中的整数, $j,j'$ 是 $[0,m]$ 中的整数(每当我们之后使用 $(i,j) - (i',j')$ 的记法,我们都保证满足上述所有条件)。 法珞知道,对于这种结构,有一种办法可能让她找到黎瑟:法珞用左手扶住墙,手臂和墙面垂直,保持这个状态向前方走,在转弯处也保持左手一直扶墙的状态。按照这个方法她就可以环绕一周,可能与黎瑟相遇。 ![](https://cdn.luogu.com.cn/upload/pic/57058.png) 上图是样例输入中第一次询问的法珞的行走方案,在行走过程中法珞的左手必须贴住墙。 法珞一开始会给你需要维护的初始的(这层楼的)结构,之后会给你 $q$ 个请求。 + 操作 1 : 读入格式形如 $1 \ x_0 \ y_0 \ x_1 \ x_2$:法珞请求在当前结构里添加一段 $(x_0,y_0) - (x_1,y_1)$ 的墙,保证此前这段墙不存在且这段墙不在 $(0,0) - (n,m)$ 的子矩形的四条边上。 + 操作2: 读入格式形如 $2 \ x_0 \ y_0 \ x_1 \ x_2$:法珞请求在当前结构里删除一段 $(x_0,y_0) - (x_1,y_1)$ 的墙,保证此前这段墙存在且这段墙不在 $(0,0) - (n,m)$ 的子矩形的四条边上。 + 操作3: 读入格式形如 $3\ x_0 \ y_0 \ x_1\ y_1\ d_0 \ x_2 \ y_2 \ x_3 \ y_3 \ d_1$ :法珞当前在 $(x_0,y_0) - (x_1,y_1)$ 的墙的中点位置 $(\frac{x0+x1}{2},\frac{y_0 + y_1}{2})$ , $d_0$ 是一个 $[0,1]$ 中的整数,用来描述法珞在墙的哪一侧, $d_0 = 0$ 代表法珞在墙的左方/上方, $d_0 = 1$ 代表右方/下方。黎瑟当前在 $(x_2,y_2) - (x_3,y_3)$ 的墙的中点位置 $(\frac{x2+x3}{2},\frac{y_2+y_3}{2})$ 。 $d_1$ 的格式和 $d_0$ 相同。保证 $(x_0,y_0) - (x_1,y_1)$ 和 $(x_2,y_2) - (x_3,y_3)$ 这两段墙存在,且法珞和黎瑟的位置都落在 $(0,0) - (n,m)$ 的子矩形的内部。求法珞按照题目所述的方法找到黎瑟要走过多少长度( $(i,j) - (i',j')$ 这段墙的长度为 $1$,半段墙(由于起点和终点都在墙的中点处)的长度是 $\frac{1}{2}$ )。

输入输出格式

输入格式


输入共 $2n+q$ 行。 第一行三个整数 $n$ 、$m$ 、$q$ ,意义如题目中所示。 接下来的 $n$ 行,每行 $m-1$ 个 $[0,1]$ 中的整数,第 $i$ 行第 $j$ 列的整数为 $1$ 表示 $(i,j) - (i-1,j)$ 这一段有墙,为 $0$ 则表示 $(i,j) - (i - 1,j)$ 这一段没有墙。 接下来的 $n-1$ 行,每行 $m$ 个 $[0,1]$ 中的整数,第 $i$ 行第 $j$ 列的整数为 $1$ 表示 $(i,j) - (i,j-1)$ 这一段有墙,为 $0$ 则表示 $(i,j) - (i,j-1)$ 这一段没有墙。 接下来的 $q$ 行,每行一个操作,格式如题目中所示。

输出格式


对于每个询问,输出法珞按照题目所述的方法找到黎瑟要走过多少长度,**如果法珞按照题目所述的方法无法找到黎瑟则输出 $-1$ 。**

输入输出样例

输入样例 #1

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

输出样例 #1

11
16

说明

对于 10% 的数据, $5 \le n,m \le 50$ , $1 \le q \le 2000$ 。 对于另外 30% 的数据,没有 1 操作。 对于另外 30% 的数据,保证在任意时刻若法珞和黎瑟站在任意输入格式中合法的位置,法珞都可以和黎瑟相遇。 对于100%的数据,$5 \le n,m \le 500$ , $1 \le q \le 2 \times 10^5$ 。