对于一个由左括号 ( 和右括号 ) 构成的字符串，我们称它是匹配括号串，当且仅当其中左右括号数量相等，且存在一种将左右括号一一匹配的方案，使得任何匹配中左括号在右括号前面，且任何两对匹配对应的区间要么不相交，要么有包含关系。

对于两个匹配括号串 $X,Y$，我们称 $X$ 能生成 $Y$ 当且仅当可以从 $X$ 中删除若干对（可以为 $0$ 对）匹配的括号对得到 $Y$。

给定长度为 $n$ 的匹配括号串 $A$ 和长度为 $m$ 的匹配括号串 $B$，有 $q$ 次询问，每次询问给定 $l_1,r_1,l_2,r_2$，求 $A[l_1,r_1]$ 能否生成 $B[l_2,r_2]$，保证这两个子串都是匹配括号串。

输入格式

从标准输入读入数据。

第一行：三个整数 $n,m,q$。

第二行：一个长度为 $n$ 的字符串 $A$。

第三行：一个长度为 $m$ 的字符串 $B$。

接下来 $q$ 行：每行四个整数 $l_1,r_1,l_2,r_2$，描述一个询问。

输出格式

输出到标准输出。

输出共 $q$ 行：若答案为肯定，输出 YES；若答案为否定，输出 NO。

样例

输入

8 8 8
(()())()
(())()()
1 6 1 4
1 6 1 6
1 6 5 8
2 5 1 4
2 5 5 8
7 8 7 8
1 8 1 8
1 8 1 6

输出

YES
NO
YES
NO
YES
YES
NO
YES

子任务

对于全部数据：$1\leq n,m,q\leq 12000,\ 1\leq l_1< r_1\leq n,\ 1\leq l_2< r_2\leq m$，保证 $A,B$ 以及每次询问的子串都是匹配括号串。

$\text{Subtask 1}(15\%)$：$n,m\leq 30$。

$\text{Subtask 2}(20\%)$：$n,m\leq 100$。

$\text{Subtask 3}(15\%)$：$n,m\leq 600$。

$\text{Subtask 4}(20\%)$：$n,m\leq 4000$。

$\text{Subtask 5}(30\%)$：无特殊限制。