You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本题为寻找豆汁 ( Easy ) 的困难版本，其中部分题面不同，为避免歧义，重新阅读题面。

题目描述

由于 ymr 十分想喝豆汁，所以小劉帮他买了一杯放在了一个地方，但是 ymr 去拿豆汁的途中路途坎坷，有许多的障碍，小 H 想帮助 ymr 获取豆汁，所以放置了若干传送阵帮助 ymr ，现在 ymr 向你询问他是否能够拿到豆汁。

现在假设 ymr 和豆汁都存在在一个棋盘上，其中每个格子用 S_{i , j} 表示。

当且仅当 S_{i , j} 只会为 ' . ' , ' # ' , 其中' . '表示可以通行，' # '表示不可通过。

传送阵用 ( a , b ) ( c , d ) 表示可以从点 ( a , b ) 处传送至 ( c , d ) 处，所有的传送阵均为单向的。

确保 ymr 和豆汁，传送阵所在处不会出现障碍。

ymr 起初在 ( x , y ) 处，他可以向八个方向行进: 上，下，左，右，左上，左下，右上，右下

若 ymr 能够拿到豆汁则输出 "YES"，否则输出 "NO"。

输入描述

每组测试数据描述如下：

第一行两个数字 n , m , k ( 1 <= n , m , k <= 1000 ) 分别表示棋盘的长和宽，传送阵的个数。

接下来 n 行，每行 m 个字符 S_{i , j}。

接下来 k 行，每行四个数字 a_i , b_i , c_i , d_i ( 1 <= a_i , c_i <= n) ( 1 <= b_i , d_i <= m) 表示传送阵的起点和终点。

最后一行四个数字 x₁ , y₁ , x₂ , y₂ ( 1 <= x₁ , x₂ <= n) ( 1 <= y₁ , y₂ <= m) 分别表示 ymr 所在的坐标，豆汁所在的坐标。

输出描述

若 ymr 能够拿到豆汁则输出 "YES"，否则输出 "NO"。

输出 "yes","yeS","yEs',"yES","Yes","YeS","YEs"均视为与 "YES" 一致，"No","no","nO"均视为与 "NO" 一致。

样例

3 3 1
...
.##
.#.
1 1 3 3
1 1 3 3

YES