B. Winning Record
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have been hired by the Texas Exes to build an app that helps Longhorns fans track the performance of the football team over time. One of the features they've requested is for the user to select a range of historical games; the app should then tell them whether or not the Longhorns had a winning record within that range of games.

Write an algorithm that implements this feature.

Input

The first line of input contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n, k \leq 100\,000)$$$: the number of games in the database and the number of ranges that you need to analyze.

The next line is a string of exactly $$$n$$$ characters. Each character is either W or L, indicating that the Longhorns won or lost the game. The wins and losses are listed in chronological order from oldest game to newest.

The final $$$k$$$ lines are ranges to analyze. Each range contains two space-separated integers $$$i$$$ and $$$j$$$ $$$(1 \leq i \leq j \leq n)$$$.

Output

Print a string of $$$k$$$ characters, representing the results of your analysis for each of the $$$k$$$ ranges (in order).

For each range, print a Y if the Longhorns won more games than they lost between games $$$i$$$ and $$$j$$$ inclusive. Otherwise, print N.

(Note in particular that if the Longhorns won and lost the same number of games in a range, you should print N.)

Example
Input
11 5
WWLWLWLLLWW
1 1
1 3
6 11
2 6
1 11
Output
YYNYY