蚂蚁 Carl 回来了！在游历了一些金字塔之后，Carl 决定研究一些算法，并发明了一种用于解决网格迷宫的新颖算法。其工作方式如下：

• Carl 从迷宫中的某个位置开始，面向右侧，想要到达目标方格。
• 当 Carl 尚未到达目标方格时：
  • 如果 Carl 可以向左转 90 度并面对一个空方格，他将向左转 90 度，然后向前移动一个方格。
  • 否则，如果 Carl 可以向前移动一个方格，他将这样做。
  • 否则，他将向右转 90 度。

Carl 想知道这个算法是否有效。请帮他检查一下！

输入格式

第一行包含两个整数 $r$ 和 $c$ ($1 \le r, c \le 50$)，表示迷宫的大小（行数、列数）。方格 $(1, 1)$ 是迷宫的左上角。

下一行包含两个整数 $i_{start}$ 和 $j_{start}$ ($1 \le i_{start} \le r, 1 \le j_{start} \le c$)，表示 Carl 的起始位置，位于第 $i_{start}$ 行，第 $j_{start}$ 列。

下一行包含两个整数 $i_{end}$ 和 $j_{end}$ ($1 \le i_{end} \le r, 1 \le j_{end} \le c$)，表示 Carl 想要到达的目标位置，位于第 $i_{end}$ 行，第 $j_{end}$ 列。保证 Carl 的起始位置和目标位置不同。

接下来的 $r$ 行，每行包含一个长度为 $c$ 的字符串，仅由 0 或 1 组成。如果字符为 1，则该方格有障碍物，无法通行；否则该方格为空。保证 Carl 的起始位置和目标位置均为空。

输出格式

输出一个整数，如果 Carl 可以从起始位置到达目标位置，则输出 1，否则输出 0。

样例

输入 1

4 5
1 1
4 5
00111
10100
10111
10000

输出 1

1

输入 2

3 3
1 1
3 3
001
001
110

输出 2

0