My first attempt use string hashing to check the palindrome with Segment Tree lazy prop.
O(Q*K*logK*logN), esp. for the update query and it's TLE 11

However, using Manacher algorithm with Segment Tree you can achieve O(Q*(K+lgN))

Little help:
- WA#3 : You're likely answering too much. (K involved)
- WA#9 : N=10^5, overflow somewhere