Muhammad TATU Urganch filiali 1-kurs talabasi. 1-kurs bo’lishiga qaramasdan Muhammad o’z mehnati bilan TUIT Urgench Branch#2 jamoasi tarkibiga kirishga muvaffaq bo’ldi. Bir kuni Murodjon Muhammadga topshiriq berib uni yana bir marta sinab ko’rishga qaror qildi. Bu topshiriq quyidagicha: Murodjon Muhammadga kichik lotin harflaridan iborat satr aytadi va o’zi bu satrni barcha qism satrlarini qog’ozga yozadi. Keyin bu satrlarni leksikografik jihatdan saralab yangi ro’yxatni hosil qiladi (teng satrlar bo’lsa joylashgan indeksi kichigi ro’yxatda oldin joylashadi) va Muhammaddan [L, R] oraliqda joylashgan qism satr leksikografik jihatdan saralangan ro’yxatda nechanchi o’rinda turganini so’raydi. Masalan “aaa” satr uchun quyidagi ro’yxatni hosil qilamiz: a, a, a, aa, aa, aaa va satrda [2, 3] oraliqda joylashgan qism satrni ko’radigan bo’lsak u 5-o’rinda joylashgan. Hozir Muhammad bu savol ustida bosh qotirmoqda. Sizdan ham bu savolga javob topish so’raladi.

Kiruvchi ma’lumotlar: Birinchi satrda kichik lotin harflaridan iborat s satr (1 ≤ |s| ≤ 10⁵). Keyingi satrda ikkita butun son L va R (1 ≤ L ≤ R ≤ |s|).

Chiquvchi ma’lumotlar: Bitta butun son berilgan qism satrning leksikografik jihatdan saralangan ro’yxatdagi o’rni.

happynewyear

6 8

ababababababc

7 10

Izoh:

s satrning qism satrlari deb barcha 0 ≤ i ≤ j ≤ n - 1 (bu yerda n − s satrning uzunligi) juftliklar uchun si,si+1…sj lardan tuzilgan satrlarga aytiladi.

a satr b satrdan leksikografik jihatdan kichik dayiladi, agar shunday bir i indeks topilib barcha (1 ≤ j < i) j lar uchun a[j] = b[j] va a[i] < b[i] shart bajarilsa. Ya'ni bunday satrlarga quyidaglarni misol qilishimiz mumkin.

a = ”abbdf”, b = “abbea”

a = ”abc”, b = “abcd”

yuqoridagi misollarda a satr b satrdan leksikografik jihatdan kichik.