All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Mark has recently started studying string algorithms. So, as to gauge his knowledge, Lucy challenges him to a task.
"Given a string s, answer several times a query to determine whether a substring s[i, j] (inclusive) is palindromic or not.", said Lucy in a confident tone!
As smart as Mark is, he was able to instantly find the solution!
Now, Mark has challenged little Lucy to do the same task by reversing a specific substring beforehand. As Lucy is still just a novice, she asks for your help.
You have to write a program that answers Q queries on a string S.
Each query contains four integers (i, j, k, l). For every query, first reverse the substring s[i, j] (inclusive) and then report if substring s[k, l] (inclusive) is a palindrome.
Note that the reversal operations are only for the specific query and should not persist for further queries. Please check the explanation section for better understanding.
The first line of input file contains string S. The next line contains an integer Q.
Each of the following Q lines each contain 4 space separated integers i, j, k and l.
Output exactly Q lines, each containing the result of corresponding query as "Yes" or "No".
- 1 ≤ |S| ≤ 105
- 1 ≤ Q ≤ 333333
- 1 ≤ i ≤ j ≤ |S|
- 1 ≤ k ≤ l ≤ |S|
- S contains only the characters 'a' to 'z'
ababa 4 2 3 3 4 1 2 3 4 1 3 3 5 2 4 1 5
Yes No Yes Yes
Query 1: The string becomes aabba. The queried substring is bb, which is a palindrome.
Query 2: The string becomes baaba. The queried substring is ab, which is not a palindrome.
Query 3: The string becomes ababa. The queried substring is aba, which is a palindrome.
Query 4: The string becomes ababa. The queried substring is ababa, which is a palindrome.
- Here, a substring [i, j] is defined as the string formed by characters s[i], s[i+1],..., s[j].
- A palindrome is a sequence of characters which reads the same backward or forward. For example, aba, abba are palindromes, while abab and abcd are not palindromes.
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.