There is an infinite $$$2$$$-dimensional grid. Initially, a robot stands in the point $$$(0, 0)$$$. The robot can execute four commands:

U — move from point $$$(x, y)$$$ to $$$(x, y + 1)$$$;
D — move from point $$$(x, y)$$$ to $$$(x, y - 1)$$$;
L — move from point $$$(x, y)$$$ to $$$(x - 1, y)$$$;
R — move from point $$$(x, y)$$$ to $$$(x + 1, y)$$$.

You are given a sequence of commands $$$s$$$ of length $$$n$$$. Your task is to answer $$$q$$$ independent queries: given four integers $$$x$$$, $$$y$$$, $$$l$$$ and $$$r$$$; determine whether the robot visits the point $$$(x, y)$$$, while executing a sequence $$$s$$$, but the substring from $$$l$$$ to $$$r$$$ is reversed (i. e. the robot performs commands in order $$$s_1 s_2 s_3 \dots s_{l-1} s_r s_{r-1} s_{r-2} \dots s_l s_{r+1} s_{r+2} \dots s_n$$$).

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the length of the command sequence and the number of queries, respectively.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of characters U, D, L and/or R.

Then $$$q$$$ lines follow, the $$$i$$$-th of them contains four integers $$$x_i$$$, $$$y_i$$$, $$$l_i$$$ and $$$r_i$$$ ($$$-n \le x_i, y_i \le n$$$; $$$1 \le l \le r \le n$$$) describing the $$$i$$$-th query.

Output

For each query, print YES if the robot visits the point $$$(x, y)$$$, while executing a sequence $$$s$$$, but the substring from $$$l$$$ to $$$r$$$ is reversed; otherwise print NO.

Note

In the first query of the first sample, the path of the robot looks as follows:

$\text{[math]}$

In the second query of the first sample, the path of the robot looks as follows:

$\text{[math]}$

In the third query of the first sample, the path of the robot looks as follows:

$\text{[math]}$

Robot Queries

Examples