Степан дуже полюбляє паліндроми. Паліндромом називається рядок, який однаково читається як зліва направо, так і справа на ліво.
Підпаліндромом даного рядка називається послідовність символів з даного рядка, які не обов'язково йдуть поспіль, і є паліндромом. Наприклад, ABA є підпаліндромом рядка ACBFADEF.
Степан вирішив пограти з рядком. Він придумує рядок і бере з даного рядка підрядок (послідовність символів з по , що йдуть поспіль) та визначає паліндром максимальної довжини. Потім бере новий підрядок і вже з нього визначає паліндром максимальної довжини, і так разів.
Напишіть програму, яка допоможе Степану.
Перший рядок вхідного файлу містить рядок довжиною не більше 100 символів з великих букв латинського алфавіту. Другий рядок містить одне число (1 \le k \le 10) — кількість разів, яку Степан зіграв з даним рядком. Наступні рядків містять по два числа та — номери першого та номер останнього символа підрядка.
Вихідний файл має містити рядків, у кожному з яких має бути записана довжина максимального підпаліндрома та через пробіл сам максимальний підпаліндром для відповідних та у вхідних даних. Якщо таких підпаліндромів кілька, то виведіть любий з них.
Example 1