B. Компьютерийн гар

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Вася компьютер дээр бичиж сурж байлаа. Түүнд ер бусын компьютерийн гар байдаг. Энэ гарны мөр бүр нь $m$ товчнууд агуулсан $n$ мөртэй тэгш өнцөгт хэлбэртэй юм. Үүнээс гадна хоёр төрлийн товчнууд байдаг. Тэдгээрийн зарим нь латин жижиг үсэгнүүдтэй ба зарим нь стандарт компьютерийн гарны "шифт" товчлуур шиг жижиг үсэгнүүдийг том болгож ажилладаг.

Вася нэг гараараа нэг эсвэл хоёр товчлуурыг дарж чаддаг. Гэхдээ товчнуудын төвүүдийн хоорондох Евклидийн зай нь $x$-ээс хэтрээгүй тохиолдолд тэр хоёр товчийг дарж чадна. Товчнуудын тал бүр нь $1$-тэй тэнцүү квадрат хэлбэртэй гэж үзнэ. Мөн зэргэлдээ товчнуудын хооронд ямар ч хоосон зай байхгүй байна.

Вася их залхуу хүү учраас нэг гараараа чипс идээд нөгөө гараараа бичих гэж оролдож байна. Гэхдээ зарим нэг үсэг болон түүнтэй хамгийн ойр байгаа "шифт" товч хоёрын хоорондын зай нь $x$-ээс их бол зөвхөн нэг гараараа тухайн үсгийг бичиж чадахгүй. Энэ тохиолдолд тэр нөгөө гараа ашиглах хэрэгтэй болно. Вася үсгээ бичээд нөгөө гараараа буцаад чипсээ иднэ.

Танд Васягийн компьютерийн гар болон текст өгөгдсөн байна. Васягийн нөгөө гараа ашиглах хамгийн бага тоог ол.

Оролт

Эхний мөр нь $n$, $m$, $x$ ($1 ≤ n, m ≤ 30, 1 ≤ x ≤ 50$) гурван бүхэл тоог агуулна.

Дараагийн $n$ мөрүүд нь компьютерийн гарны бүх товчлууруудыг илэрхийлнэ. Мөр бүр нь зайгаар тусгаарласан $m$ ширхэг товчны тодорхойлолтыг агуулна. Товчлууруудын үсгүүдийг харгалзан жижиг үсгүүдээр тэмдэглэнэ. "Шифт" товчлуурыг "S" тэмдэгтээр тэмдэглэнэ.

Дараагийн мөрөнд текстийн урт $q$ $(1 ≤ q ≤ 5 \cdot 10^{5})$ байна. Сүүлийн мөрөнд $q$ ширхэг латин том, жижиг үсгүүдээс бүрдсэн $T$ текст агуулагдана.

Гаралт

Хэрвээ Вася текстийг бичиж чадсан бол түүний нөгөө гараа ашигласан хамгийн бага тоог хэвлэнэ. Эсрэг тохиолдолд "-1" гэж хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2 2 1
ab
cd
1
A
Гаралт
-1
Оролт
2 2 1
ab
cd
1
e
Гаралт
-1
Оролт
2 2 1
ab
cS
5
abcBA
Гаралт
1
Оролт
3 9 4
qwertyuio
asdfghjkl
SzxcvbnmS
35
TheQuIcKbRoWnFOXjummsovertHeLazYDOG
Гаралт
2

Тэмдэглэл

Эхний жишээнд компьютерийн гаранд "Шифт" товч байхгүй учраас "$A$" үсгийг бичих боломжгүй.

Хоёр дахь жишээнд компьютерийн гаранд $e$ товч байхгүй учраас "$e$" үсгийг бичих боломжгүй.

Дөрөв дэх жишээнд "T", "G" үсэгнүүдийг нэг гараараа бичих боломжгүй. Бусад тэмдэгтүүдийг нэг гараараа хэвлэх боломжтой. Эдгээр үсэгнүүд текстэд хоёр удаа гарч ирж байгаа учраас хариулт $2$ байна.

Сэтгэгдлүүдийг ачааллаж байна...