Masala #0142

Xotira 64 MB Vaqt 1000 ms
14

Bilag’on va palindromlar

Bilag’on palindrom satrlarni juda yaxshi ko’radi. Shuning uchun u ayrim so’zlarning harflaridan foydalangan holda hosil qilish mumkin bo’lgan eng uzun palindromlarni yasaydi. Masalan bobo so’zidan u obbo yoki boob so’zlarini, robocontest so’zidan esa otrto, torot, otbto, tobot, ototo, tooot,  otcto, tocot, otnto, tonot, oteto, toeot, otsto, tosot so’zlarini hosil qila oladi.


Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida kichik lotin harflaridan iborat S(1 ≤ |S| ≤ 105) satri kiritiladi, ikkinchi satrda T(1 ≤ T ≤ 105) butun son va keyingi T ta qatorda so’rov beriladi. Har bir so’rovda L va R(1 ≤ L ≤ R ≤ |S|) sonlari kiritiladi.


Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir so’rov uchun alohida qatorda agarda Bilag’onga S satrning [L,…,R] qism satri berilganida u jami necha xil eng uzun palindrom satr hosil qilishi mumkinligini chop eting. Bu son juda katta bo’lishi mumkin, shuning uchun siz bu sonning 109+7 ga bo’lgandagi qoldig’ini chop eting.


Misollar
# input.txt output.txt
1
bobo
1
1 4
2
2
robocontest
2
1 11
2 6
14
3