Given a string s and m queries . Each query consists of (l,r) where 1 <= l <= r <= n(size of string).

You need to print whether l to r is a palindromic string or not.

A string can be called palindrome if its reverse is same as itself . Ex – “aba” .Input Format

First line contains n Second lines contains a string of length n. Next line contains m where m is the number of queries . Next m lines contains two integers l,r as described in the question.Constraints

n <= 1000

m <= 100000Output Format

for every query from l to r print “YES” if s[l…..r] is palindrome else print “NO” without quotes in a new line.Sample Input

```5
abbac
2
1 4
2 4```

Sample Output

```YES
NO```

Explanation

s[1….4]=”abba”, it is a palindrome.

## Solution – Java Program

```import java.util.*;
public class Main {
public static void main (String args[]) {
Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

String str = scan.next();

int t = scan.nextInt();

char[] c = str.toCharArray();

boolean[][] dp = new boolean[n][n];

for(int col=1;col<=n;col++)
{
for(int row=0;row<=n-col;row++)
{
if(col <= 2)
{
if(c[row] == c[row+col-1])
{
dp[row][row+col-1] = true;
}
}
else if(c[row] == c[row+col-1])
{
dp[row][row+col-1] = dp[row+1][row+col-2];
}
}
}
while(t-- > 0)
{
int left = scan.nextInt();
int right = scan.nextInt();
if(dp[left-1][right-1])
System.out.println("YES");
else
System.out.println("NO");
}
}
}
```