প্রচলিত বিশ্বাস আছে যে, গুপ্ত দ্বীপ ট্রেজারল্যান্ডে অনেক অমীমাংসিত রহস্য ও অনাবিষ্কৃত গুপ্তধন রয়েছে। ক্যাপ্টেন জ্যাক এবং তার টিম গুপ্ত দ্বীপটি খুঁজে পেল। দ্বীপে কয়েকদিন ঘোরাঘুরি করার পর পাহাড়ের ওপর সে একটি বন্ধ গুহা দেখতে পেল। তার বিশ্বাস ছিল যে গুপ্তধন বন্ধ গুহার ভেতরেই ছিল। গুহার দেয়ালে লেখা ছিল যে "এই মন্ত্রটি পড়লে গুহার দরজা খুলে যাবে।" মন্ত্রটিও সেখানে লেখা ছিল, কিন্তু কিছু অক্ষর অনুপস্থিত ছিল।হতাশ হয়ে সে নিচে তাকাল এবং নিচে কিছু অক্ষর লেখা দেখতে পেল। সে অক্ষরগুলো জায়গামত বসিয়ে সে মন্ত্রটি সম্পূর্ণ করল এবং গুহার দরজা খুলে গেল। দেখা যাক তুমিও এর সমাধান করতে পারো কিনা।
ধর অসম্পূর্ণ মন্ত্রটি হল $S$
. মন্ত্রটিতে ইংরেজি ছোটহাতের অক্ষর অথবা $"?"$
চিহ্নটি থাকতে পারে। তোমাকে $K$
টি হারানো অক্ষর দেওয়া হবে। মন্ত্রটির প্রত্যেক $"?"$
চিহ্নের পরিবর্তে এক বা একাধিক হারানো অক্ষর বসাতে হবে। সবগুলো হারানো অক্ষর অবশ্যই ব্যবহার করতে হবে। যেহেতু এভাবে অনেকভাবে মন্ত্রটি বানানো সম্ভব, তাই আমরা সেই মন্ত্রটি বের করতে চাচ্ছি যেটা বর্ণানুক্রমে সবচেয়ে ছোট।
উদহারণসরূপ,
যদি $S$
= $\textbf{c?b?b}$
,$K$
= $2$
এবং $2$
টি হারানো অক্ষর হল $\textbf{ae}$
.
মন্ত্রটি হতে পারে $\textbf{cabeb}$
অথবা $\textbf{cebab}$
. এই দুটোর মধ্যে $\textbf{cabeb}$
বর্ণানুক্রমে ছোট.
আবার ধরো যদি $S$
= $\textbf{?cde}$
,$K$
= $3$
এবং $3$
টি হারানো অক্ষর হল $\textbf{baa}$
.
মন্ত্রটি হতে পারে $\textbf{aabcde}$
অথবা $\textbf{abacde}$
অথবা $\textbf{baacde}$
. এগুলোর মধ্যে $\textbf{aabcde}$
বর্ণানুক্রমে সবচেয়ে ছোট।
প্রথম লাইনে একটি পূর্ণসংখ্যা $T$
দেওয়া থাকবে যেটি টেস্টকেস সংখ্যা নির্দেশ করে।
প্রতিটি টেস্টকেসের প্রথম লাইনে একটি স্ট্রিং $S$
দেওয়া থাকবে। স্ট্রিংটিতে কমপক্ষে একটি $"?"$
চিহ্ন থাকবেই।
পরের লাইনটিতে একটি পূর্ণসংখ্যা $K$
থাকবে, যার পরে $K$
টি ইংরেজি ছোটহাতের অক্ষর দেওয়া থাকবে। স্ট্রিংটিতে যতগুলো $"?"$
চিহ্ন থাকবে, $K$
এর মান তার চেয়ে সমান বা বড় হবে।
$1 \leq T \leq 1000$
$K \leq 10$
প্রতিটি স্ট্রিং $S$
এ $10$
টির বেশি অক্ষর থাকবে না।
$1 \leq T \leq 100$
$K \leq 100$
প্রতিটি স্ট্রিং $S$
এ $100$
টির বেশি অক্ষর থাকবে না।
$1 \leq T \leq 500$
$K \leq 20000$
প্রতিটি স্ট্রিং $S$
এ $20000$
টির বেশি অক্ষর থাকবে না।
প্রতিটি টেস্টকেসের জন্য মন্ত্রটি আলাদা আলাদা লাইনে প্রিন্ট করতে হবে।
Input | Output |
---|---|
5 t?ph 1 o ?in?o 2 gb ?ouris? 2 tt ?cde 2 ab ??cde 2 ab | toph bingo tourist abcde abcde |
যদি আমাদের দুইটা সমান সাইজ এর স্ট্রিং $A$
এবং $B$
থাকে, $B$
এর থেকে $A$
বর্ণানুক্রমে ছোট হবে যদি এমন একটি পজিশন $i$
থাকে যেখানে $A_1$
=$B_1$
, $A_2$
=$B_2$
,..., $A_{i-1}$
=$B_{i-1}$
এবং $A_i$
<$B_i$
.