Palindrome and Queries

তোমাকে শুধুমাত্র ছোট-হাতের ইংরেজি অক্ষর সম্বলিত N টা স্ট্রিং এর একটি অ্যারে A এবং Q টা কুয়েরি দেয়া হবে। প্রতি কুয়েরিতে সবচেয়ে বড় প্যালিন্ড্রোমিক সাবস্ট্রিং এর লেংথ বের করতে হবে যেটা কমপক্ষে L টা স্ট্রিং এবং সর্বোচ্চ R টা স্ট্রিং এর মধ্যে আছে। যদি সেরকম কোনো প্যালিন্ড্রোমিক সাবস্ট্রিং না থাকে, তাহলে 0 প্রিন্ট করতে হবে।

প্যালিন্ড্রোম হলো যেসকল শব্দসমুহ যেগুলো সামনের এবং পেছনের দিক থেকে পড়লে একই থাকে। যেমনঃ madam, abba.সাবস্ট্রিং হলো একটি স্ট্রিং এর এক বা একাধিক কন্টিনিউয়াস ক্যারেক্টার নিয়ে গঠিত স্ট্রিংসমূহ। যেমনঃ abc স্ট্রিং এর ৬ টি সাবস্ট্রিং আছেঃ a, ab, abc, b, bc, c.প্যালিন্ড্রোমিক সাবস্ট্রিং হলো সেসকল সাবস্ট্রিং যা সামনের এবং পেছনের দিক থেকে পড়লে একই থাকে। যেমনঃ taka স্ট্রিংটিতে ৪(চার) টি ইউনিক প্যালিন্ড্রোমিক সাবস্ট্রিং আছেঃ t, a, k, aka.

Input

ইনপুটে একাধিক টেস্টকেস থাকবে। প্রতি টেস্টকেসের প্রথম লাইনে দুইটি পূর্ণসংখ্যা N এবং Q দেয়া থাকবে। পরবর্তী N লাইনের প্রতিটিতে একটি করে স্ট্রিং থাকবে, যেটার i তম Ai স্ট্রিং নির্দেশ করে। পরবর্তী Q লাইনের প্রতিটিতে *দুইটি *পূর্ণসংখ্যা L এবং R থাকবে যা প্রবলেমের বর্ণনাতে বলা আছে।

1 ≤ T≤ 15
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ L ≤ R ≤ N
1 ≤ |Ai| ≤ 105
প্রতি টেস্টকেসে সকল স্ট্রিং এর দৈর্ঘ্যের যোগফল ≤ 106

১ম সাবটাস্ক, ১০ পয়েন্টের জন্যঃ
1 ≤ T≤ 15, 1 ≤ N ≤ 10, 1 ≤ Q ≤ 100, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 20প্রতি টেস্টকেসে সকল স্ট্রিং এর দৈর্ঘ্যের যোগফল ≤ 100

২য় সাবটাস্ক, ৩০ পয়েন্টের জন্যঃ
1 ≤ T≤ 15, 1 ≤ N ≤ 100, 1 ≤ Q ≤ 10000, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 4100প্রতি টেস্টকেসে সকল স্ট্রিং এর দৈর্ঘ্যের যোগফল ≤ 10000

৩য় সাবটাস্ক, ৬০ পয়েন্টের জন্যঃ আসল কনস্ট্রেইন্টস.

Output

প্রতিটি কুয়েরির জন্য একটি লাইন প্রিন্ট করতে হবে যার i তম লাইন i তম কুয়েরির উত্তর নির্দেশ করে।

Sample

Input	Output
1 3 6 aaac aaabbbbbb abbaaa 1 1 1 2 1 3 2 2 2 3 3 3	6 6 6 2 3 3

অনেক বড় ডাটাসেট, ফাস্টার ইনপুট/আউটপুটের পদ্ধতি ব্যবহার করো।