B. Гүкиз ба тэмдэгт мөр

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

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

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

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

Профессор Гүкиз тэмдэгт мөрнүүдийг байгаа хэвээр нь байлгах дургүй. Тэрээр зарим үсэгнүүдийн байрыг солин шинэ тэмдэгт мөр үүсгэх дуртай.

Гүкизэд $a$, $b$, $c$ гэсэн гурван тэмдэгт мөр байна. Тэрээр $a$ тэмдэгт мөрийн зарим үсгүүдийн байрыг нь солих замаар гарган авсан $k$ тэмдэгт мөр нь хоорондоо огтлолцохгүй аль болох олон $b$, $c$ дэд тэмдэгт мөрүүдийг агуулж байхыг хүсчээ.

$x$ тэмдэгт мөрийн дэд тэмдэгт мөр гэдэг бол $x$ тэмдэгт мөрөнд дэхь дараалсан үсэгнүүдийг хэлнэ. Хэрвээ $x$ тэмдэгт мөрний $i$ дэхь үсэг хоёр дэд тэмдэгт мөрөнд хоёуланд нь орсон байвал энэ хоёр дэд тэмдэгт мөрийг огтлолцож байна гэж үзнэ.

Гүкизийн сурагчид бодлогыг бодож чадаагүй учир тэрээр урам нь их хугарчээ. Та тэдэнд туслаж $k$ тэмдэгт мөрийг олж чадах уу?

Оролт

Эхний мөрөнд $a$, хоёр дахь мөрөнд $b$, гурав дахь мөрөнд $c$ тэмдэгт мөрнүүд тус тус өгөгдөнө. Энд $1 ≤ |a|, |b|, |c| ≤ 10^{5}$ байх бөгөөд $|s|$ гэдэг нь $s$ тэмдэгт мөрний уртыг илэрхийлнэ.

Бүх гурван тэмдэгт мөр Англи жижиг үсэгнээс бүтнэ. $b$ болон $c$ хоорондоо адил байж болно.

Гаралт

Нөхцөлд тохирох $k$ тэмдэгт мөрийг хэвлэ. Хэрэв олон боломжит хариу байвал аль нэгийг нь хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
aaa
a
b
Гаралт
aaa
Оролт
pozdravstaklenidodiri
niste
dobri
Гаралт
nisteaadddiiklooprrvz
Оролт
abbbaaccca
ab
aca
Гаралт
ababacabcc

Тэмдэглэл

Гурав дахь жишээний хариунд $3$-н огтлолцоогүй дэд тэмдэгт мөр байна $[1,2]$ ("ab"), $[3,4]$ ("ab"), $[5,7]$ ("aca"). Энэ жишээнд олон хариу байгаа бөгөөд тэдгээрийн нэг нь "acaababbcc" юм.

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