E. Хатагтай Хадсоны шарвин

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

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

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

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

Хатагтай Хадсон өөрийн алдартай шарвингаа нэлээн удаан хийгээгүй бөгөөд одоо тэрээр ахин хийхээр болжээ. Тэрээр саяхан $m$ ширхэг шинэ жор сурсан бөгөөд эдгээрийг туршиж үзэхээс хүлээж тэсэхгүй байв. Эдгээр жорууд нь $n$ ширхэг орцоос тогтож байв. Хатагтай Хадсон эдгээр орцуудаа $0$-ээс $n - 1$ хүртэлх бүхэл тоонуудаар дугаарлагдсан ваарнуудад хийн гал тогоондоо хадгалдаг байжээ (орц болгон нь ялгаатай ваар дотор байна). Түүнчлэн ваар болгон нь өөрийн агуулж буй орцод харгалзах үнэ болох $a_{i}$ гэсэн бүхэл тоог агуулсан байна.

Бид $i$-р шарвингийн жорын хувьд 3-н утгыг мэдэж байна: $d_{i}$, $s_{i}$, $c_{i}$. Энд $d_{i}$ болон $c_{i}$ нь бүхэл тоонууд байх бөгөөд $s_{i}$ нь $d_{i}$ суурьтай тооллын систем дээр бичигдсэн нэгэн бүхэл тооны бүтэц байх юм. Тооны бүтэц нь цифрүүд, Латин үсгүүд (9-өөс их цифрүүдийг тэмдэглэхийн тулд) болон асуултын тэмдгүүд агуулсан байх юм. $d_{i}$ суурьтай тооллын систем дээрх $x$ тооны хувьд хэрэв бид $s_{i}$ тооны бүтэц доторх асуултын тэмдгүүдийг цифрүүд болон үсгүүдээр солин $x$ тоог гарган авч чадаж байвал (0-ээс эхэлсэн байвал 0-үүдийг тооцохгүй байж болно) уг тооны бүтэцтэй тохирч байна гэж үзэх юм. Илүү дэлгэрэнгүй тайлбарлавал: асуултын тэмдэг болгон нь яг нэг цифр эсвэл үсгээр солигдох юм. Хэрэв бид бүх асуултын тэмдгийг сольсны дараа 0-ээр эхэлсэн тоо гарган авсан байвал бид эдгээр 0-үүдийг устгаж болно. Жишээлбэл $11$ суурьтай тооллын систем дэх $40A9875$ гэсэн тоо нь "$??4??987?$" гэсэн тооны бүтэцтэй тохирч байх бөгөөд $4A9875$ гэсэн бүтэцтэй тохирохгүй байх юм.

$i$-р жорын дагуу шарвин хийхийн тулд хатагтай Хадсон $d_{i}$ суурьтай тооллын систем дэх бичлэг нь $s_{i}$ тооны бүтэцтэй тохирч байх бүх тоонуудыг сонгох бөгөөд эдгээр тоонуудаар дугаарлагдсан ваарнуудтай орцуудаар шарвин хийх юм. Жорын удирдлагын тоо $z_{i}$ гэдэг нь $c_{i}$ болон уг жорд хэрэглэгдсэн бүх ваарнуудын үнийн үржвэрүүдийн нийлбэр байх юм. Өөрөөр хэлбэл: байх бөгөөд энд $j$ нь $d_{i}$ суурьтай тооллын систем дэх бичлэг нь $s_{i}$ тооны бүтэцтэй тохирч байх бүх тоонуудыг илэрхийлэх юм.

Хатагтай Хадсон эдгээр удирдлагын тоонуудад нэг их анхаарал өгөхгүй байгаа боловч тэрээр тэдгээрийн хамгийн бага анхны тоон хуваагчийг ихээхэн сонирхож байв. Таны даалгавар: $i$-р жор бүрийн хувьд $z_{i}$-ын хамгийн бага анхны тоон хуваагчийг олно уу. Хэрэв уг хуваагч нь $100$-аас их байвал -1 гэж хэвлэнэ үү.

Оролт

Эхний мөрөнд ганц бүхэл тоо $n$ ($1 ≤ n ≤ 10^{4}$) өгөгдөнө. 2-дахь мөрөнд зайгаар тусгаарлагдсан орцуудын үнэ болох $a_{0}, a_{1}, ..., a_{n - 1}$-ууд өгөгдөх ба энд $a_{i}$ нь бүхэл тоо байна ($1 ≤ a_{i} ≤ 10^{18}$).

3-дахь мөрөнд ганц бүхэл тоо $m$ ($1 ≤ m ≤ 3*10^{4}$) өгөгдөх ба энэ нь Хатагтай Хадсоны сурсан жорын тоог илэрхийлнэ.

Дараагийн $m$ ширхэг мөрөнд жоруудыг дүрслэх бөгөөд мөр болгонд нэг жорыг дүрсэлнэ. Жорыг дүрслэхдээ эхлээд танд 10-тын тооллын систем дээр бичигдсэн бүхэл тоо $d_{i}$ ($2 ≤ d_{i} ≤ 16$) өгөгдөнө. Дараа нь зайгаар тусгаарлагдан $s_{i}$ бүтэц өгөгдөх ба энэ нь $1$-ээс $30$ хүртэлх (эдгээр нь мөн орно) урттай, "$0$"-ээс "$9$" хүртэлх цифрүүд, "$A$"-аас "$F$" хүртэлх үсгүүд болон "$?$" тэмдгээс тогтох тэмдэгт мөр байна. "$A$"-аас "$F$" хүртэлх үсгүүдийг $10$-аас $15$ хүртэлх цифрүүдэд харгалзаж байгаа гэж үзнэ үү. Мөн бүтэц доторх бүх цифрүүд (үсгээр илэрхийлэгдэж байгаа цифрүүд ч гэсэн) нь $d_{i}$-аас эрс бага байх ёстой юм. Үүний дараа зайгаар тусгаарлагдан бүхэл тоо $c_{i}$ өгөгдөх ба энэ нь мөн адил 10-тын тооллын систем дээр тэмдэглэгдсэн байна ($1 ≤ c_{i} ≤ 10^{18}$).

С++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг бүү хэрэглэнэ үү. Үүний оронд use cin, cout, strings эсвэл %I64d гэсэн тодорхойлогчийг хэрэглэхийг илүүд үзнэ үү.

Гаралт

Жор бүрийн хувьд удирдлагын тоо нь хуваагдах хамгийн бага анхны тоог олох бөгөөд уг анхны тоог дан мөрөнд хэвлэнэ үү. Хэрэв уг тоо нь $100$-аас их байвал -1 гэж хэвлэнэ үү.

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

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

Оролт
1
1
1
2 ? 1
Гаралт
2
Оролт
4
2 3 5 7
4
2 ?0 11
2 ?1 13
2 0? 17
2 1? 19
Гаралт
3
2
23
2
Оролт
1
1000000000000000000
1
16 ?????????????? 1
Гаралт
-1

Тэмдэглэл

Эхний жишээнд 2-тын тооллын систем дэх бүх нэг оронтой тоонууд нь тохирч байх юм. Бидэнд ганцхан ваар өгөгдсөн ба үүний үнэ нь $1$-тэй тэнцүү байх бөгөөд $c$ тоо нь мөн $1$-тэй тэнцүү байна. Иймд удирдлагын тоо нь $2$ болох бөгөөд $2$-ын хамгийн бага анхны тоон хуваагч нь $2$ байх юм.

2-дахь жишээнд нийтдээ $0$-ээс $3$ хүртэл дугаарлагдсан $4$ ширхэг ваар байх бөгөөд үнэ нь харгалзан $2$, $3$, $5$ болон $7$-той тэнцүү байх юм (эхний 4-н анхны тоонууд байна). Жор болгоны хувьд тоонууд нь 2 оронтой байх юм. Эхний жорын хувьд 2-дахь цифр нь үргэлж $0$ байна, 2-дахь жорын хувьд 2-дахь цифр нь үргэлж $1$ байна, 3-дахь жорын хувьд эхний цифр нь заавал $0$ байна, харин 4-дэх жорын хувьд эхний цифр нь үргэлж $1$ байх юм. Эцэст нь удирдлагын тоонууд нь дараах байдалтай байна: эхний жорын хувьд $2 × 5 + 11 = 21$ (хамгийн бага анхны тоон хуваагч нь $3$), 2-дахь жорын хувьд $3 × 7 + 13 = 44$ (хамгийн бага анхны тоон хуваагч нь $2$), 3-дахь жорын хувьд $2 × 3 + 17 = 23$ (хамгийн бага анхны тоон хуваагч нь $23$) байх бөгөөд 4-дэх жорын хувьд $5 × 7 + 19 = 54$ (хамгийн бага анхны тоон хуваагч нь $2$) байх юм.

3-дахь жишээнд тоо нь 14-н оронгоос тогтох бөгөөд 16-тын тооллын системд бичигдсэн байх юм. $0$ гэсэн дугаар (бидэнд өгөгдсөн цор ганц ваарын дугаар) нь тохирч байх бөгөөд энэ үед удирдлагын тоо нь $10^{18} + 1$-тэй тэнцүү болно. Уг тооны хамгийн бага анхны тоон хуваагч нь $101$-тэй тэнцүү байх бөгөөд иймд та -1 гэж хэвлэх ёстой юм.

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