B. Баавгай ба шахалт

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

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

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

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

Лимак бол жижиг туйлын баавгай юм. Туйлын баавгайнууд урт тэмдэгт мөрүүдэд дургүй ба иймд тэд тэдгээрийг шахах дуртай байдаг. Мөн Лимак нь маш залуу гэдгийг мэдэх хэрэгтэй ба тэрээр зөвхөн Англи цагаан толгойн эхний 6-н үсгийг мэднэ: '$a$', '$b$', '$c$', '$d$', '$e$' болон '$f$'.

Танд $q$ ширхэг боломжит үйлдлийн олонлог өгөгдөнө.Лимак тэдгээрийг ямар ч дарааллаар хийж болох ба ямар ч үйлдэл нь хэдэн ч удаа хийгдэж болно. $i$-дахь үйлдэл нь 2 урттай тэмдэгт мөр $a_{i}$ болон 1 урттай тэмдэгт мөр $b_{i}$-аар дүрслэгдэнэ. $q$ ширхэг боломжит үйлдлүүдийн аль ч 2 нь ижилхэн $a_{i}$ тэмдэгт мөртэй байхгүй.

Лимак-д $s$ тэмдэгт мөр байхад хэрэв $s$-ын эхний 2 үсэг нь 2 үсэгтэй тэмдэгт мөр $a_{i}$-тай таарч байвал тэрээр $s$ дээр $i$-дахь үйлдлийг хийж чадах юм. $i$-дахь үйлдлийг хийхдээ $s$-ын эхний 2 үсгийг авч хаяад тэнд нь тэмдэгт мөр $b_{i}$-г байрлуулна.Илүү дэлгэрэнгүйг тэмдэглэлээс харна уу.

Та магадгүй нэг үйлдлийг хийхэд $s$ тэмдэгт мөрийн уртыг яг $1$-ээр багасгаж байгааг анзаарсан байх. Мөн, зарим нэг үйлдлүүдийн олонлогийн хувьд тэмдэгт мөр нь ахин цааш шахагдахгүй байна, учир нь эхний 2 үсэг нь ямар ч $a_{i}$-тай таарахгүй байх юм.

Лимак $n$ урттай тэмдэгт мөрөөс эхлэн $n - 1$ үйлдэл хийсний эцэст нэг-үсэгт тэмдэгт мөр "$a$"-г гарган авахыг хүсэж байгаа юм. Тэгвэл тэрээр "$a$"-г гаргаж чадах анхны тэмдэгт мөрийг хэчнээн янзаар сонгож болох вэ? Лимак зөвхөн өөрийн мэддэг үсгээ ашиглаж чадахыг санаарай.

Оролт

Эхний мөрөнд анхны тэмдэгт мөрийн урт болон боломжит үйлдлүүдийн тоог илэрхийлэх 2 бүхэл тоо $n$ болон $q$ ($2 ≤ n ≤ 6$, $1 ≤ q ≤ 36$) өгөгдөнө.

Дараагийн $q$ мөрөнд боломжит үйлдлүүдийг дүрсэлнэ. Тэдгээрийн $i$-дахь нь 2 тэмдэгт мөр $a_{i}$ болон $b_{i}$ ($|a_{i}| = 2, |b_{i}| = 1$) агуулна. Мөн $i ≠ j$-ын хувьд $a_{i} ≠ a_{j}$ байх ба бүх $a_{i}$ болон $b_{i}$ нь зөвхөн эхний 6-н Англи жижиг үсгүүдээс тогтоно.

Гаралт

Лимак зөвхөн оролтод өгөгдсөн үйлдлүүдийг хийснээр "$a$" тэмдэгт уруу хувиргаж чадах $n$ урттай тэмдэгт мөрүүдийн тоог хэвлэнэ.

Орчуулсан: Баатархүү

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

Оролт
3 5
ab a
cc c
ca a
ee c
ff d
Гаралт
4
Оролт
2 8
af e
dc d
cc f
bc b
da b
eb a
bb b
ff c
Гаралт
1
Оролт
6 2
bb a
ba a
Гаралт
0

Тэмдэглэл

Эхний жишээнд, бид Лимак шаардагдсан "$a$" тэмдэгт мөрийг гаргаж чадах $3$ урттай анхны тэмдэгт мөрүүдийг тоолно. Ийм $4$-н тэмдэгт мөр байна: "$abb$", "$cab$", "$cca$", "$eea$". Эхний тэмдэгт дээр Лимак $1$-дэх үйлдлийг 2 удаа ("$ab$"-г дан "$a$" хүртэл өөрчилнө) хэрэглэж шахна. Эхний үйлдэл нь "$abb$"-г "$ab$" хүртэл өөрчлөх ба 2-дахь үйлдэл нь "$ab$"-г "$a$" хүртэл өөрчилнө.

Бусад 3-н тэмдэгт мөрүүд нь дараах байдлаар шахагдана:

  • "$cab$" "$ab$" "$a$"
  • "$cca$" "$ca$" "$a$"
  • "$eea$" "$ca$" "$a$"

2-дахь жишээнд, цорын ганц зөв анхны тэмдэгт нь нь "$eb$" байна учир нь энэ нь шуудхан "$a$" хүртэл шахагдаж чадна.

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