Rotation and Queries

তোমাকে ইংরেজী ছোটহাতের অক্ষর নিয়ে গঠিত একটা স্ট্রিং S এবং N টি কুয়েরি দেয়া হবে। প্রতি কুয়েরিতে তোমাকে লেক্সিকোগ্রাফিক্যালি সবচেয়ে বড় স্ট্রিং রোটেশন বের করতে হবে যেটাতে ইনপুট স্ট্রিং এর X লেংথের সাফিক্স সাবস্ট্রিং হিসেবে থাকবে। উদাহরণস্বরূপ, স্যাম্পলে দেয়া bca স্ট্রিং এর ৩ টা রোটেশন আছে, যথাক্রমে bca (০ তম রোটেশন), cab (১ নম্বর রোটেশন), abc (২ নম্বর রোটেশন)। এই রোটেশনগুলোর মধ্যে দুইটা রোটেশনে ca (ইনপুট স্ট্রিং এর ২ লেংথের সাফিক্স) সাবস্ট্রিং হিসেবে আছে। আবার এই দুইটা রোটেশন এর মধ্যে পরেরটা লেক্সিকোগ্রাফিক্যালি বড়। তাই, স্যাম্পল i/o-র প্রথম টেস্টকেসের দ্বিতীয় কুয়েরী (যেই কুয়েরিতে X = 2) এর উত্তর ১ (ইনডেক্স অফ রোটেশন)।

যদি আউটপুট হিসেবে পাওয়া একাধিক রোটেশন লেক্সিকোগ্রাফিক্যালি সমান হয়, তাহলে যেই রোটেশন এর ইনডেক্স সবচেয়ে ছোট সেটা আউটপুট দিতে হবে।

একটা স্ট্রিং এর পরপর নেয়া কয়েকটা ক্যারেক্টার নিয়ে সাবস্ট্রিং গঠিত হয়। উদাহরণস্বরূপ, abc স্ট্রিং এর ৫ টি অশূণ্য সাবস্ট্রিং আছেঃ a, b, c, ab, bc, abc.

একটা স্ট্রিং এর সাবস্ট্রিংসমূহ যেগুলো সর্বশেষ ক্যারেক্টারটিকেও রাখে, সেগুলোকে ওই স্ট্রিং এর সাফিক্স বলে। উদাহরণস্বরূপ, abc স্ট্রিং এর ৩ টা সাফিক্স আছেঃ abc, bc, c.

একটা স্ট্রিং এর প্রথম ক্যারেক্টার কে রিমুভ করে শেষে যুক্ত করাকে স্ট্রিং রোটেশন বলেন। উদাহরণস্বরূপ, abc স্ট্রিং এর ৩ টা রোটেশন আছেঃ-

• abc স্ট্রিঙ্গটি নিজেই তার ০-তম রোটেশন

• ১ম রোটেশন bca.

• ২য় রোটেশন cab.

এখানে আমরা i-তম রোটেশন এর ব্যাপারটাকেই ইনডেক্স অফ রোটেশন হিসাবে সংজ্ঞায়িত করছি।

লেক্সিকোগ্রাফিক্যাল অর্ডার মানে ডিকশনারীর অর্ডার। উদাহরণস্বরূপ, ডিকশনারিতে trick শব্দটি tracks শব্দের পরে আসে কারণ, ইংরেজী অক্ষর সিস্টেমে ‘i ‘ অক্ষরটি ‘a’ অক্ষর এর পরে আসে। মনে রাখা উচিত যে, এই অর্ডারটি স্ট্রিং এর সাইজের ভিত্তিতে নয়। সুতরাং লেক্সিকোগ্রাফিক্যালি সবচেয়ে বড় স্ট্রিং রোটেশন মানে হলো সবগুলো রোটেশন এর মধ্যে যেই রোটেশনটি ডিকশনারিতে সবার পরে আসবে।

Input

ইনপুটে একাধিক টেস্টকেস থাকবে। ইনপুটের প্রথম লাইনে একটা ইন্টিজার T থাকবে, যেটা টেস্টকেস সংখ্যা নির্দেশ করে। প্রতি টেস্টকেসের প্রথম লাইনে তোমাকে একটা স্ট্রিং S এবং একটি ইন্টিজার N দেয়া হবে, যা যথাক্রমে ইনপুট স্ট্রিং এবং কুয়েরির সংখ্যা নির্দেশ করে। এরপরে N লাইনের প্রতিটিতে একটি ইন্টিজার X থাকবে, যা সাফিক্স এর লেংথ নির্দেশ করে।

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ X ≤ Length of the input string S

প্রথম সাবটাস্ক (১০ পয়েন্ট) এর জন্যঃ

• 1 ≤ N ≤ 100

• 1 ≤ Length of the string S ≤ 100

দ্বিতীয় সাবটাস্ক (২৫ পয়েন্ট) এর জন্যঃ

• 1 ≤ N ≤ 3000

• 1 ≤ Length of the string S ≤ 3000

তৃতীয় সাবটাস্ক (৬৫ পয়েন্ট) এর জন্যঃ

• 1 ≤ N ≤ 100000

• 1 ≤ Length of the string S ≤ 100000

Output

প্রতি টেস্টকেসের জন্য তোমাকে “Case C:” (কোটেশন মার্ক ছাড়া) প্রিন্ট করতে হবে, যেখানে C টেস্টকেস নম্বর নির্দেশ করে। তারপর পরবর্তী N লাইনের প্রতিটিতে একটি করে ইন্টিজার থাকবে, যেটা এক-একটি কুয়েরির উত্তর, যা লেক্সিকোগ্রাফিক্যালি সবচেয়ে বড় স্ট্রিং রোটেশন যেটাতে ইনপুট স্ট্রিং এর X লেংথের সাফিক্স সাবস্ট্রিং হিসেবে আছে, সেটার ইনডেক্স নম্বর। মনে রাখতে হবে যে, যদি আউটপুট হিসেবে পাওয়া একাধিক রোটেশন লেক্সিকোগ্রাফিক্যালি সমান হয়, তাহলে যেই রোটেশন এর ইনডেক্স সবচেয়ে ছোট সেটা আউটপুট হিসেবে দিতে হবে।

আউটপুট ফরম্যাট ভালোভাবে বুঝতে স্যাম্পল ইনপুট আউইটপুট দেখো।

Sample

Input	Output
2 bca 3 1 2 3 abbdef 6 1 2 3 4 5 6	Case 1: 1 1 0 Case 2: 5 4 3 2 1 0