Петяа хоккейд маш их дуртай. Нэг өдөр тэр хоккейн тэмцээн үзэж байлаа. Тэрээр хоккейн багийн нэрийг солихоор сонгогдсон ч болоосой гэж мөрөөдөж эхлэв. Иймээс Петяад багийн жинхэнэ нэр $w$ болон $s_1, s_2, ..., s_n$ хориотой дэд тэмдэгтийн цуваанууд өгөгдсөн. Эдгээр бүх тэмдэгтэн цуваанууд нь Латин цагаан толгойн том, жижиг үсгүүдээс тогтоно. $w$ тэмдэгтэн цуваа нь $|w|$ урттай ба тэдэгтүүд нь 1-ээс $|w|$ хүртэл дугаарлагдсан.

Эхлээд Петяа $w$ тэмдгэтэн цуваан дахь бүх хориотой дэд тэмдэгт мөрүүдийн байрлалыг олох хэрэгтэй. Дэд тэмдэгт мөрүүдийн хайхад том жижиг үсгүүд хамаагүй. Тэгэхээр "aBC", "ABc" хоёр адил гэсэн үг.

Дараа нь Петяа тэдгээр олдсон байрлалуудын хамрах бүх үсгүүдийг солих ёстой. Дүрмээр бол хэрэв $w$ тэмдэгтэн цуваан дахь $i$ байрлалын хувьд, том жижиг харгалзахгүй харьцуулалт хийхэд $w[l...r]$ тэмдэгтэн цуваа $s_1, s_2, ..., s_n$ цуваануудад агуулагддаг байх $l, r (1 <= l <= i <= r <= |w|)$ хос индекс олддог бол $i$ байрлал дахь үсэг ямар нэгэн өөр үсгээр орлуулагдах хэрэгтэй. Орлуулах үйл явцад том, жижиг нь хэвээр үлдэх ёстой. Петяа хориотой тэмдэгтэн цуваанд хамрагдаагүй үсгүүдийг солиж чадахгүй.

Хоккейн тоглогчдод $letter$ (том эсвэл жижиг) үсгийг азтайд тооцогддог. Тиймээс Петяа өөрчлөлтийг хийхдээ аль болох $letter$ үсгийг олон орсон байхаар хийх ёстой. Петяад тийм үр дүнд үүсэх тэмдэгтийг гаргаж авахд туслаарай. Хэрэв хэд хэдэн тийм тэмдэгт мөрүүд үүсэж байвал цагаан толгойн дарааллаар хамгийн эхнийг нь үүсгэ.

Орлуулах үйл явцыг дахин давтахгүй ганц л хийнэ гэдгийг анхаар. Энэ нь хэрэв Петяа орлуулгуудыг хийсний даараа тэмдэгтэн цуваа шинэ муу тэмдэгтэн цуваануудыг агуулж эхлэх юм бол Петяа тэдгээрийг ерөөс тоохгүй.

Оролт

Хориотой тэмдэгтэн цуваануудын тоог заах ганц $n (1 <= n <= 100)$ бүхэл тоог эхний мөр агуулна. Дараачийн $n$ мөрүүд тэдгээр дэд тэмдэгтэн цуваануудыг агуулах болно. Дараагийн мөрөнд $w$ тэмдэгтэн цуваа байна. Бүх $n + 1$ мөрүүд урт нь 100-аас хэтрэхгүй Латин цагаан толгойн том, жижиг үсгүүдээс бүтсэн хоосон биш тэмдэгтэн цувааг агуулах болно. Хамгийн сүүлийн мөрөнд $letter$ үсэг байна.

Гаралт

Петяагийн үүсгэсэн $letter$ үсгийг хамгийн их агуулсан тэмдэгтэн цувааг нэг мөрөнд гарга. Хэрэв хэдэн хариу байгаа бол цагаан толгойн дарааллаар хамгийн эхнийхийг гаргах ёстой.

Цагаан толгойн харьцуулалт нь орчин үеийн программчлалын хэлний < оператороор хийгдэнэ. Хэрэв $a$ нь $b$-ийн угтвар эсвэл $a_i < b_i$ ба $(1 <= j < i)$ байх бүх $j$-ийн хувьд $a_j = b_j$ байдаг $i (1 <= i <= |a|)$ олддог бол $a$ нь $b$-ээс цагаан толгойн дарааллаар бага байна. $|a|$ нь $a$ тэмдэгтэн цувааны уртыг тэмдэглэнэ.