迷路の小L

题号：NC214320
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小 $\text L$ 说自己很喜欢跑步。
小 $\text{D}$ 把小 $\text L$ 跑步的地方抽象成一个 $\mathop n$ 行 $\mathop m$ 列的平面矩形，其中左上角为点 $(\text 1,1)$ ，右下角为点 $\text(n,m)$ 。对于每一个点 $\text(i,j)$ ，都有一个值 $a_{i,j}$ ， $a_{i,j}=1$ 表示该点为墙， $a_{i,j}=0$ 表示该点可以通过；一共有 $\mathop s$ 个点是墙，即 $s=\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j}$ 。特别地，边界上的点 $\big($ 满足 $i=\text 0$ 或 $i=n+\text 1$ 或 $j=\text 0$ 或 $j=m+\text 1$ 的点 $\text(i,j)$ $\big)$ 也视作墙，但不计入 $\mathop s$ 。在地图上能且只能朝垂直和水平四个方向跑动。但是小 $\text L$ 很呆，总是迷路，因此一般只会沿一个方向跑动，当且仅当她撞墙时，她会改变方向（向后，向左或向右）跑动。
开始时小 $\text L$ 站在点 $\text(p,q)$ 。由于过多的撞墙会使得小 $\text L$ 变得更呆，可她又是如此热爱跑步，所以现在，小 $\text{D}$ 发出了 $\mathop T$ 次各自独立的询问，对于第 $\mathop i$ 次询问，他想知道小 $\text L$ 以 $\text(p,q)$ 为起点，最多能撞墙 $k_i$ 次时，最多能跑过多少个点。
注意，同一个点可以重复计数，起点也计数。在起点时可以向任意方向跑动。撞墙是指在当前点，若再沿原先方向跑动 $\text 1$ 步，所在点为墙；特殊地，若她在满足上述条件的点结束跑步，则不视为撞墙。

输入描述:

输入共行。
第一行包含个正整数和个非负整数。
接下来行，每行包含个非负整数，其中第行第个数表示。
接下来行，第行包含一个非负整数。

输出描述:

输出共行，第行包含一个正整数，表示对于第次询问，小最多能跑过的点数。

示例1

输入

复制

5 5 1 1 1 10
0 0 1 0 1
1 0 0 0 1
0 1 0 0 1
1 0 0 0 1
1 1 0 0 0
3

输出

复制

说明

。

示例2

输入

复制

5 5 1 3 1 10
0 0 1 0 1
1 0 0 0 1
0 1 0 0 1
1 0 0 0 1
1 1 0 0 0
10

输出

复制

说明

很遗憾，但小不能跑。注意，在同一点内多次改变方向时，该点并不会被重复计数，因为小不能用转圈代替跑步。