অর্থনৈতিকভাবে স্বাবলম্বী হওয়ার জন্য স্যাটার্ন নতুন এক ব্যবসার ধান্দা করেছে, গাছের ব্যবসা।
প্রথমে স্যাটার্ন দুই ধরণের গাছ বানাবেঃ টাইপ-১ গাছ এবং টাইপ-২ গাছ। স্যাটার্ন যে জগতে বাস করে, সেখানে কিছু ফল মিশায়ে সহজেই একটা গাছ বানানো যায়। প্রত্যেকটা আলাদা রকমের ফল কোন ইউনিক নাম্বার দ্বারা চিহ্নিত। স্যাটার্নের অসীম পরিমাণ কাল টাকা আছে, তাই সে যে কোন রকমের ফল যত ইচ্ছা কিনতে পারে। কিন্তু কোন এক টাইপের গাছে কয়টা ফল দেওয়া যাবে তার কিছু লিমিট আছে, এই লিমিট ক্রস করলে গাছটা বাজে হয়ে যাবে।
উদাহরণস্বরূপ, ধরা যাক, টাইপ-১ গাছে সর্বোচ ৪টা আইডি-১ ফল এবং সর্বোচ্চ ৩টা আইডি-২ ফল ব্যবহার করা যায়। আর বাদবাকি যেসব আইডির ফলের কথা বলা হয়নি, সেগুলো সর্বোচ্চ ০টা ব্যবহার করা যায়। এখন, স্যাটার্ন কয়টা আলাদা আলাদা রকমের টাইপ-১ গাছ তৈরি করতে পারে? ২০টা। কারণ দুইটা গাছকে আলাদা ধরা হয় যদি তাদের মধ্যে কোন এক রকমের ফলের সংখ্যা আলাদা হয়। যেমন, ৩টা আইডি-১ ফল ও ১টা আইডি-২ ফল দিয়ে তৈরি করা একটা গাছ এবং ৩টা আইডি-১ ও ২টা আইডি-২ ফল দিয়ে তৈরি করা আরেকটা গাছ একই রকমের না, গাছ দুইটা আলাদা আলাদা। খেয়াল করো, স্যাটার্ন কিন্তু একটা গাছে ০ সংখ্যক আইডি-১ বা আইডি-২ ফল ব্যবহার করতে পারে। আরো অবাক ব্যাপার হলো, যখন সব ফলগুলোই ০ সংখ্যক দেওয়া হয়, তখনও একটা আলাদা রকমের গাছ তৈরি হয়! এজন্যই, যদি ১টা আইডি-১ এবং ২টা আইডি-২ ফল টাইপ-১ গাছের লিমিট হয়, তাহলে টোটাল ৬ রকমের টাইপ-১ গাছ তৈরি করা সম্ভব। গাছগুলোকে ০০, ০১, ০২, ১০, ১১, ১২ দ্বারা রিপ্রেজেন্ট করা যায় যেখানে ১১-এর মানে হলো এই গাছটায় ১টা আইডি-১ এবং ১টা আইডি-২ ফল ব্যবহার করা হয়েছে।
স্যাটার্ন অলরেডি টাইপ-১ এবং টাইপ-২ গাছগুলোর লিমিট জানে। সে প্রথম দিনে যত রকমের সম্ভব, সব রকমের টাইপ-১ এবং টাইপ-২ গাছ তৈরি করবে। স্যাটার্নের অদ্ভুত জগৎটাতে প্রত্যেক দিনের টাইপ-১ গাছগুলো পরের দিনে নতুন রকমের টাইপ-২ গাছ হয়ে যায়, আর প্রত্যেক দিনের টাইপ-২ গাছগুলো ভেঙ্গে যেয়ে নতুন রকমের টাইপ-১ এবং টাইপ-২ গাছ তৈরি করে।
উদাহরণস্বরূপ, যদি প্রথম দিনে ৫ রকমের টাইপ-১ গাছ এবং ৪ রকমের টাইপ-২ গাছ থাকে, তাহলে পরের দিনে ৫টা টাইপ-১ গাছ ৫টা নতুন টাইপ-২ গাছে পরিবর্তিত হয়ে যাবে এবং ৪টা টাইপ-২ গাছ ভেঙ্গে ৪টা নতুন টাইপ-১ এবং ৪টা নতুন টাইপ-২ গাছ তৈরি করবে। সূতরাং, দ্বিতীয় দিনে ৪টা টাইপ-১ গাছ এবং ৯টা টাইপ-২ গাছ থাকবে।
এখন, P, Q এবং টাইপ-১ ও টাইপ-২ গাছগুলোর ফলের লিমিট দেওয়া থাকবে, তোমাকে P-তম দিনে যতগুলো টাইপ-২ গাছ আছে এবং Q-তম দিনে যতগুলো টাইপ-২ গাছ আছে - সেই দুই সংখ্যার গ.সা.গু (গরিষ্ঠ সাধারণ গুণনীয়ক) বের করতে হবে। যেহেতু সংখ্যাটা বেশ বড় হতে পারে, সংখ্যাটাকে M দিয়ে ভাগ করলে যে ভাগশেষ থাকে (modulo M) তা উত্তর হিসেবে প্রিন্ট করতে হবে।
Input
ইনপুট শুরু হবে দুইটা পূর্ণসংখ্যা N1 এবং N2 দিয়েঃ যথাক্রমে টাইপ-১ এবং টাইপ-২ গাছে কয় রকমের ফল ব্যবহার করা যাবে। এর পরের লাইনে **N1**টা স্পেস-সেপারেটেড পূর্ণসংখ্যা দেওয়া থাকবে, প্রত্যেকটা সংখ্যা কোন পৃথক রকমের ফলের টাইপ-১ গাছে সর্বোচ্চ লিমিট প্রকাশ করবে। একইভাবে পরের লাইনে **N2**টা স্পেস-সেপারেটেড পূর্ণসংখ্যা দেওয়া থাকবে, প্রত্যেকটা কোন পৃথক রকমের ফলের টাইপ-২ গাছে সর্বোচ্চ লিমিট প্রকাশ করবে। শেষ লাইনে ৩টা পূর্ণ সংখ্যা P, Q, M দেওয়া থাকবে যেগুলোর বিস্তারিত প্রবলেম স্টেটমেন্টে আগেই বলা হয়েছে।
1 ≤ N1, N2 ≤ 104
1 ≤ কোন ফলের ম্যাক্সিমাম লিমিট ≤ 104
1 ≤ P, Q ≤ 104
|P - Q| ≤ 2
1 ≤ M ≤ 109
Output
P-তম দিনে যতগুলো টাইপ-২ গাছ আছে এবং Q-তম দিনে যতগুলো টাইপ-২ গাছ আছে - সেই দুই সংখ্যার গ.সা.গু-কে M দিয়ে ভাগ করলে যে ভাগশেষ থাকে তা প্রিন্ট করো।
Sample
| Input | Output |
|---|---|
2 3 1 2 1 1 1 1 2 3 | 2 |
The maximum limits of the fruits for type-1 trees are 1 and 2. So there can 6 kinds of type-1 trees possible (this example is also shown in problem description). Similarly, the number of distinct type-2 trees is 8. So in day 1, there will be 6 type-1 trees and 8 type-2 trees. In day 2, the 6 type-1 trees will become 6 type-2 trees and the 8 type-2 trees will split into 8 type-1 trees and 8 type-2 trees. So, in day 2, there will be 8 type-1 trees and 14 type-2 trees. Thus, the numbers of type-2 trees in day 1 and day 2 are 8 and 14. The GCD of these two numbers is 2 and 2 modulo 3 is also 2, so the answer is 2. | |
