题目背景

小U是一名珠宝大盗，他从未失手过。这次，他接到一个任务，是去偷一个“稀世之宝”————硅硼铝钙石（我也不知道是什么，反正贵就对了），当然它的主人在存放它的房间里设置了多个摄像头以及红外线报警器，所以他想请你算一算能否从地面取到它。

题目描述

在一个n * n的房间里，有m1个摄像头和m2个红外线报警器，每个摄像头扫描的范围分别是A1 * A1,A2 * A2…… ，每个红外线报警器长度都是L（在输入中体现） ，若有重叠则会叠加。(珠宝位置用数字“999”代替,小U当前位置用字符“k”代替)

输入格式

共n+4行:第1行输入n；第2~n+1行为房间俯视图;第n+2行输入m1,m2;第n+3行输入A1,A2,A3……第n+4行输入L。

若m1 或 m2 为0，则所对应的行输入“00000”。

输出格式

若可以，则：

共n+1行，前n行输出俯视图（路径为1，没走过的为0）； 第n+1行输出共走了几步。

若不可以，则输出

     By air
     

以及到第几步时受阻

若有多个解则输出最优解

样例 #1

样例输入 #1

6
0 0 0 k 0 1
0 1 1 0 0 1
0 1 1 1 0 0
1 1 1 2 1 0
1 1 1 2 1 0
0 0 0 999 0
2 3
3 2
2

样例输出 #1

0 0 0 1 0 0
0 0 0 1 1 0
0 0 0 0 1 1
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 1 1
8

样例 #2

样例输入 #2

4
0 k 0 0
0 0 1 1
1 1 2 2
0 0 0 999
1 1
2
4

样例输出 #2

By air
1

样例 #3

样例输入 #3

2
k 0
0 999
0 0
00000
00000

样例输出 #3

1 0
1 1
2

提示

0<n<100000

m1<50000

m2<50000

0<Ai<50000

0<L<50000