For a string consisting of left parentheses ( and right parentheses ), we call it a balanced parenthesis string if and only if the number of left and right parentheses are equal, and there exists a way to match each left parenthesis with a right parenthesis such that in every pair, the left parenthesis precedes the right one, and any two matched pairs either do not intersect or one is contained within the other.

For two balanced parenthesis strings $X$ and $Y$, we say $X$ can generate $Y$ if and only if $Y$ can be obtained by deleting zero or more matched pairs of parentheses from $X$.

Given a balanced parenthesis string $A$ of length $n$ and a balanced parenthesis string $B$ of length $m$, there are $q$ queries. Each query provides $l_1, r_1, l_2, r_2$, and you are asked to determine whether $A[l_1, r_1]$ can generate $B[l_2, r_2]$. It is guaranteed that both substrings are balanced parenthesis strings.

Input

Read data from standard input.

The first line contains three integers $n, m, q$.

The second line contains a string $A$ of length $n$.

The third line contains a string $B$ of length $m$.

The next $q$ lines each contain four integers $l_1, r_1, l_2, r_2$, describing a query.

Output

Output to standard output.

Output $q$ lines: if the answer is affirmative, output YES; if the answer is negative, output NO.

Examples

Input

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

Output

YES
NO
YES
NO
YES
YES
NO
YES

Subtasks

For all data: $1\leq n,m,q\leq 12000,\ 1\leq l_1< r_1\leq n,\ 1\leq l_2< r_2\leq m$, and it is guaranteed that $A$, $B$, and the substrings in each query are balanced parenthesis strings.

$\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\%)$: No additional constraints.