Бидэнд хайрцаг ба түлхүүрийг илэрхийлэх $p$, $q$ гэсэн хувьсагчид ($q$ хувьсагч нь зөвхөн "0" ба "1" тэмдэгтүүдээс тогтоно) байгаа болог. Түлхүүрийг ашиглан хайрцагнаас нууцлагдсан зурвасыг дараах алгоритмаар гарган авдаг байя:

i = 0;  
j = 0;  
s = <>;  
давталт (i нь p тэмдэгт мөрийн уртаас бага бол)
{  
    хэрэв (q[j] == 1) бол, s тэмдэгт мөрийн баруун талд p[i] тэмдэгтийг нэм;  
    i, j хувьсагчуудын утгыг 1-ээр нэм;  
    хэрэв (j хувьсагчийн утга q тэмдэгт мөрийн урттай тэнцүү) бол, j = 0;        
}

Өгөгдсөн псевдо кодонд $i$, $j$ нь бүхэл тоон утга, $s$ нь тэмдэгт мөр, '=' нь утга оноох үйлдэл, '==' нь харьцуулах үйлдэл, '[]' тухайн дугаар дахь тэмдэгтийг заах зүйлдэл, '<>' нь хоосон тэмдэгт мөр болно. Бид бүх тэмдэгт мөр дэх тэмдэгтүүд нь 0-ээс эхлэн дугаарлагдсан гэж үзэв.

Энэ алгоритмыг програмчилж бичих нь амархан харагдаж байгаа биз. Тиймээс таны даалгавар арай өөр байх буюу өгөгдсөн $p$ хайрцагнаас $s$ зурвасыг гарган авж болох $k$ урттай түлхүүрүүдээс цагаан толгойн дарааллаараа хамгийн эхэнд байхыг нь олох юм. Зарим тохиолдолд ийм шаардлагыг хангах түлхүүр олдохгүй байж болно.

Оролт

Оролтын эхний $2$ мөрөнд харгалзан хайрцаг ба зурвасыг илтгэх $p$, $s$ тэмдэгт мөрүүд ($1 ≤ |p| ≤ 10^{6}$, $1 ≤ |s| ≤ 200$) өгөгдөнө. Эдгээр тэмдэгт мөрүүд нь $32$-оос $126$ хүртэлх ASCII кодтой ямар ч тэмдэгтийг агуулж болно.

$3$ дахь мөрөнд түлхүүрийн урт болох нэг бүхэл тоо $k$ ($1 ≤ k ≤ 2000)$ байна.

Гаралт

Хайж буй түлхүүрийг хэвлэнэ. Түлхүүр нь $k$ урттай, зөвхөн "0", "1" тэмдэгтүүдээс тогтсон тэмдэгт мөр байх ёстой. Хэрэв түлхүүр олдохгүй бол дан ганц "0" тэмдэгтийг хэвлэнэ.

$x = x_{1}x_{2} ... x_{p}$ ба $y = y_{1}y_{2}... y_{q}$ гэсэн хоёр тэмдэгт мөрийн хувьд дараах тохиолдлуудын аль нэг нь биелэж байвал $x$ тэмдэгт мөрийг $y$-ээс цагаан толгойн дарааллын хувьд эхэнд байна гэж үзнэ:

• $p < q$ ба $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{p} = y_{p}$ байвал

• $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{r} = y_{r}$ ба $x_{r+1} < y_{r+1}$ байх $(0 ≤ r < min(p, q))$ байх $r$ бүхэл тоо оршин байвал (Тэмдэгтүүд нь ASCII кодын дугаараараа эрэмбэлэгдэнэ).