+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مجید، کودک دوست‌داشتنی و گوگولی قصه ما علاقه زیادی به جمع کردن ماژیک دارد. مجید در خانه اش $N$ تا ماژیک دارد که هر کدام از آن‌ها رنگی دارند که آن رنگ را با یک عدد نشان می‌دهیم. حال مسئله‌ای ذهن مجید را مشغول کرده است که از کدام رنگ کمترین تعداد ماژیک را دارد. از آنجایی که مجید بسیار کوچک است و هنوز شمردن بلد نیست از شما می‌خواهیم که به مجید کمک کنید و رنگ ماژیکی که تعدادش کمتر از همه است را چاپ کنید. همچنین اگر بیش از یک رنگ داشتیم که تعداد ماژیک‌هایش کمتر مساوی از بقیه بود، بین آن رنگ‌ها، آن رنگی را چاپ کنید که عددش از بقیه کمتر است. (برای فهمیدن بهتر سوال، توضیح ورودی‌های نمونه را بخوانید.) # ورودی در خط اول ورودی $N$ که تعداد ماژیک های مجید است می‌آید. در خط بعدی $N$ عدد با فاصله از هم می‌آید که عدد $i$ام نشان‌دهنده رنگ ماژیک $i$ام است. $$ 1 \le N \le 100$$ **همچنین رنگ ماژیک‌ها عددی بین ۱ تا ۱۰۰ است.** # خروجی در تنها خط خروجی یک عدد چاپ کنید که برابر شماره‌ی رنگ ماژیکی است که تعدادش کمتر از بقیه است. # مثال ## ورودی نمونه ۱ ``` 3 1 1 2 ``` ## خروجی نمونه ۱ ``` 2 ``` توضیح: مجید ۲ ماژیک با رنگ ۱ و یک ماژیک با رنگ ۲ دارد. پس کمترین رنگ،‌ رنگ ۲ است. ## ورودی نمونه ۲ ``` 5 1 2 1 3 4 ``` ## خروجی نمونه ۲ ``` 2 ``` توضیح: رنگ های ۲ و ۳ و ۴ کمترین مقدار را دارند اما چون عدد ۲ کوچکتر از ۳ و ۴ است، پس جواب برابر ۲ می‌شود.

مجید و ماژیک‌هاش

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

مجید، کودک دوست‌داشتنی و گوگولی قصه ما علاقه زیادی به جمع کردن ماژیک دارد.

مجید در خانه اش $N$ تا ماژیک دارد که هر کدام از آن‌ها رنگی دارند که آن رنگ را با یک عدد نشان می‌دهیم. حال مسئله‌ای ذهن مجید را مشغول کرده است که از کدام رنگ کمترین تعداد ماژیک را دارد.

از آنجایی که مجید بسیار کوچک است و هنوز شمردن بلد نیست از شما می‌خواهیم که به مجید کمک کنید و رنگ ماژیکی که تعدادش کمتر از همه است را چاپ کنید. همچنین اگر بیش از یک رنگ داشتیم که تعداد ماژیک‌هایش کمتر مساوی از بقیه بود، بین آن رنگ‌ها، آن رنگی را چاپ کنید که عددش از بقیه کمتر است. (برای فهمیدن بهتر سوال، توضیح ورودی‌های نمونه را بخوانید.)

ورودی🔗

در خط اول ورودی $N$ که تعداد ماژیک های مجید است می‌آید. در خط بعدی $N$ عدد با فاصله از هم می‌آید که عدد $i$ ام نشان‌دهنده رنگ ماژیک $i$ ام است. $1 \le N \le 100$ همچنین رنگ ماژیک‌ها عددی بین ۱ تا ۱۰۰ است.

خروجی🔗

در تنها خط خروجی یک عدد چاپ کنید که برابر شماره‌ی رنگ ماژیکی است که تعدادش کمتر از بقیه است.

مثال🔗

ورودی نمونه ۱🔗

3
1 1 2

خروجی نمونه ۱🔗

توضیح: مجید ۲ ماژیک با رنگ ۱ و یک ماژیک با رنگ ۲ دارد. پس کمترین رنگ،‌ رنگ ۲ است.

ورودی نمونه ۲🔗

5
1 2 1 3 4

خروجی نمونه ۲🔗

توضیح: رنگ های ۲ و ۳ و ۴ کمترین مقدار را دارند اما چون عدد ۲ کوچکتر از ۳ و ۴ است، پس جواب برابر ۲ می‌شود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و مجید در حال ساخت یک رشته طولانی از $0$ و $1$ هستند. رشته به این ترتیب ساخته می‌شود که در گام اول میلاد $1$ را می‌نویسد. از آن پس هر کس در نوبت خود رشته‌ای که تا الان ساخته شده است را در نظر گرفته و با تبدیل همه $1$ها به $0$ و همه $0$ها به $1$، رشته حاصل را در ادامه رشته قبلی می‌نویسد و سپس نوبت نفر بعد می‌شود. و این کار را تا ابد ادامه می‌دهند. برای مثال، پنج نوبت اول بازی به صورت زیر است: ابتدا میلاد $1$ را می‌نویسد و رشته در پایان این مرحله $1$ می‌شود. سپس مجید رشته فعلی که $1$ بوده را گرفته و آن را متمم می‌کند و به انتهای رشته اضافه می‌کند در پایان این مرحله رشته به صورت $10$ می‌شود. سپس میلاد $10$ را گرفته و آن را متمم می‌کند و به انتهای رشته اضافه می‌کند و در پایان این مرحله رشته به صورت $1001$ خواهد شد. سپس مجید رشته $1001$ را گرفته و با متمم کردن آن و اضافه کردنش به انتهای رشته، رشته به شکل $10010110$ می‌شود. و به همین ترتیب ساخت رشته تا ابد ادامه پیدا می‌کند. حال ما از شما می‌خواهیم با گرفتن $L$ و $R$، از کاراکتر $L$ام تا کاراکتر $R$ام رشته را برای ما چاپ کنید. # ورودی در یک خط به ترتیب $L$ و $R$ به شما داده می‌شود. $$ 1 \le L \le R \le 100\ 000$$ # خروجی از کاراکتر $L$ام تا کاراکتر $R$ام رشته را در یک خط و بدون‌ فاصله چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 2 ``` ## خروجی نمونه ۱ ``` 10 ``` ## ورودی نمونه ۲ ``` 7 10 ``` ## خروجی نمونه ۲ ``` 1001 ```

مجید، میلاد، رشته‌سازی

محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

میلاد و مجید در حال ساخت یک رشته طولانی از $0$ و $1$ هستند.

رشته به این ترتیب ساخته می‌شود که در گام اول میلاد $1$ را می‌نویسد. از آن پس هر کس در نوبت خود رشته‌ای که تا الان ساخته شده است را در نظر گرفته و با تبدیل همه $1$ ها به $0$ و همه $0$ ها به $1$ ، رشته حاصل را در ادامه رشته قبلی می‌نویسد و سپس نوبت نفر بعد می‌شود. و این کار را تا ابد ادامه می‌دهند.

برای مثال، پنج نوبت اول بازی به صورت زیر است:

ابتدا میلاد $1$ را می‌نویسد و رشته در پایان این مرحله $1$ می‌شود.

سپس مجید رشته فعلی که $1$ بوده را گرفته و آن را متمم می‌کند و به انتهای رشته اضافه می‌کند در پایان این مرحله رشته به صورت $10$ می‌شود.

سپس میلاد $10$ را گرفته و آن را متمم می‌کند و به انتهای رشته اضافه می‌کند و در پایان این مرحله رشته به صورت $1001$ خواهد شد.

سپس مجید رشته $1001$ را گرفته و با متمم کردن آن و اضافه کردنش به انتهای رشته، رشته به شکل $10010110$ می‌شود. و به همین ترتیب ساخت رشته تا ابد ادامه پیدا می‌کند.

حال ما از شما می‌خواهیم با گرفتن $L$ و $R$ ، از کاراکتر $L$ ام تا کاراکتر $R$ ام رشته را برای ما چاپ کنید.

ورودی🔗

در یک خط به ترتیب $L$ و $R$ به شما داده می‌شود. $1 \le L \le R \le 100\ 000$

خروجی🔗

از کاراکتر $L$ ام تا کاراکتر $R$ ام رشته را در یک خط و بدون‌ فاصله چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1 2

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

7 10

خروجی نمونه ۲🔗

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مجید که به تازگی برنامه‌نویسی یاد گرفته است، شبه کدی برای مرتب سازی صعودی یک آرایه به اسم $a$ به طول $n$ نوشته است که به وضوح غلط است. این تکه کد به صورت زیر است: ```c for i = 1 to n - 2 for j = 1 to n - 1 if a[j] > a[j + 1] swap(a[j], a[j + 1]) ``` میلاد جایگشتی از اعداد ۱ تا $n$ دارد که بعضی از اعداد آن مشخص نیست و به جای آن صفر گذاشته شده است. حال ما می‌خواهیم بدانیم آیا می‌توانیم جای صفرهای جایگشت، اعدادی قرار بدهیم به طوری که در انتها: 1. کد مجید نتواند جایگشت را به درستی به صورت صعودی مرتب کند. 2. هر یک از اعداد ۱ تا $n$ دقیقاً یک‌بار در آرایه آمده باشند. (برای فهمیدن بهتر، بخش ورودی و توضیح نمونه‌ها را بخوانید.) # ورودی در خط اول عدد $n$ که تعداد اعداد جایگشت است به شما داده می‌شود. در خط بعدی $n$ عدد،بین $0$ تا $n$، که با فاصله جدا شده‌اند به شما داده می‌شود که اعداد جایگشت میلاد است. $$1 \le n \le 100\ 000$$ # خروجی اگر می‌توانستیم صفر‌ها را به گونه‌ای عوض کنیم که شرایط صورت سوال را داشت در خط اول خروجی عبارت ‍‍‍‍```Yes``` و در خط بعدی جایگشت کامل را به همراه اعدادی که به جای صفرها جایگزین شده‌اند چاپ کنید. (چنانچه چندین جایگشت وجود داشت، شما به دلخواه یکی از آن‌ها را چاپ کنید.) در غیر اینصورت در یک خط عبارت ```No``` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 1 3 0 2 ``` ## خروجی نمونه ۱ ``` No ``` توضیح: تنها عددی که می‌تواند جای ۰ بگذارد عدد ۴ است که برنامه مجید می‌تواند این جایگشت را مرتب کند. ## ورودی نمونه ۲ ``` 4 0 0 0 0 ``` ## خروجی نمونه ۲ ``` Yes 4 3 2 1 ``` توضیح: اگر جایگشت فوق را به برنامه مجید بدهیم آن را به درستی مرتب نمی‌کند. توجه کنید که جایگشت فوق یکی از جواب های مسئله است؛ جایگشت‌های دیگری نیز وجود دارد که برنامه‌ی مجید روی آن‌ها درست کار نمی‌کند.

باگ کد مجید

محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

مجید که به تازگی برنامه‌نویسی یاد گرفته است، شبه کدی برای مرتب سازی صعودی یک آرایه به اسم $a$ به طول $n$ نوشته است که به وضوح غلط است. این تکه کد به صورت زیر است:

for i = 1 to n - 2  
    for j = 1 to n - 1   
        if a[j] > a[j + 1]    
            swap(a[j], a[j + 1])

میلاد جایگشتی از اعداد ۱ تا $n$ دارد که بعضی از اعداد آن مشخص نیست و به جای آن صفر گذاشته شده است.

حال ما می‌خواهیم بدانیم آیا می‌توانیم جای صفرهای جایگشت، اعدادی قرار بدهیم به طوری که در انتها:

کد مجید نتواند جایگشت را به درستی به صورت صعودی مرتب کند.
هر یک از اعداد ۱ تا $n$ دقیقاً یک‌بار در آرایه آمده باشند.

(برای فهمیدن بهتر، بخش ورودی و توضیح نمونه‌ها را بخوانید.)

ورودی🔗

در خط اول عدد $n$ که تعداد اعداد جایگشت است به شما داده می‌شود. در خط بعدی $n$ عدد،بین $0$ تا $n$ ، که با فاصله جدا شده‌اند به شما داده می‌شود که اعداد جایگشت میلاد است. $1 \le n \le 100\ 000$

خروجی🔗

اگر می‌توانستیم صفر‌ها را به گونه‌ای عوض کنیم که شرایط صورت سوال را داشت در خط اول خروجی عبارت ‍‍‍‍Yes و در خط بعدی جایگشت کامل را به همراه اعدادی که به جای صفرها جایگزین شده‌اند چاپ کنید. (چنانچه چندین جایگشت وجود داشت، شما به دلخواه یکی از آن‌ها را چاپ کنید.)

در غیر اینصورت در یک خط عبارت No را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4 
1 3 0 2

خروجی نمونه ۱🔗

No

توضیح: تنها عددی که می‌تواند جای ۰ بگذارد عدد ۴ است که برنامه مجید می‌تواند این جایگشت را مرتب کند.

ورودی نمونه ۲🔗

4
0 0 0 0

خروجی نمونه ۲🔗

Yes
4 3 2 1

توضیح: اگر جایگشت فوق را به برنامه مجید بدهیم آن را به درستی مرتب نمی‌کند. توجه کنید که جایگشت فوق یکی از جواب های مسئله است؛ جایگشت‌های دیگری نیز وجود دارد که برنامه‌ی مجید روی آن‌ها درست کار نمی‌کند.

+ محدودیت زمان: ۱ ثانیه + **محدودیت حافظه: ۳۲ مگابایت** ---------- چند صباحی است که مجید به دنبال کار در شرکت‌های برنامه‌نویسی می‌گردد، اما شرکت‌های برنامه‌نویسی به دلایل نامعلومی او را رد می‌کنند . امروز مجید تصمیم گرفته که شانس خود را برای شرکت سحاب امتحان کند، بدین منظور مجید رزومه خود را برای شرکت سحاب می‌فرستد. بعد از بررسی رزومه مجید، شرکت سحاب متوجه می‌شود که این مجید همان مجید مشهور است و در نتیجه می‌خواهند که او را برای کار در شرکت نپذیرند، اما از آنجا که مسئولین استخدام شرکت سحاب انسان‌های مهربانی هستند، یک شانس به مجید می‌دهند و به اون می‌گویند در صورتی استخدام می‌شود که بتواند از یک مسیری به شرکت سحاب برسد و در این مسیر از هر شهری حداکثر یک بار عبور کند! کشوری که مجید در آن زندگی می‌کند شامل $n$ شهر و $m$ جاده‌ی دو طرفه است، که شهرها از ۰ تا $n-1$ شماره‌گذاری شده‌اند ولی جاده‌های این کشور به طرز عجیبی طراحی شده‌اند. جاده‌ها بطور کاملاً تصادفی کشیده شده‌اند! برای هرچه بیشتر تصادفی شدن این جاده‌کشی، از الگوریتم *KISS* (مخفف *Keep It Simple Stupid*) برای ساخت اعداد تصادفی و کشیدن جاده‌ها استفاده شده‌ است. کد این الگوریتم در زبان ++C به شکل زیر است. (مقادیر اولیه‌ی متغیرهای $x$ و $y$ و $z$ و $c$ در ورودی به شما داده ‌می‌شود.) ```c++ unsigned long long x, y, z, c; unsigned long long uint32(unsigned long long i) { return i & 0xFFFFFFFF; } unsigned long long kiss() { x = uint32( 69069 * x + 12345 ); y ^= uint32(y << 13); y ^= uint32(y >> 17); y ^= uint32(y << 5); unsigned long long t = 698769069 * z + c; c = uint32(t >> 32); z = uint32(t); return uint32(x + y + z); } ``` سپس مسئولین بین شهر‌ها به صورت زیر جاده احداث کرده‌اند. (تابع `build_road_between` بین دو شهر یک جاده دوطرفه قرار می‌دهد.) ```c++ for (int i = 0; i < m; i++) { int u = kiss() % n; int v = kiss() % n; build_road_between(u , v); } ``` **دقت کنید** که ممکن است بین ۲ شهر بیش از یک جاده احداث شود و یا ممکن است از یک شهر به خودش جاده‌ای وجود داشته باشد. با توجه به اینکه مجید به دلایل نامعلومی نمی‌تواند مسیر رسیدن به سحاب را پیدا کند، از شما کمک خواسته تا بلکه شما بتوانید به او برای رسیدن به این شرکت و این شغل کمک کنید. **(به محدودیت حافظه و ورودی‌های این سوال دقت کنید، حافظه به گونه‌ای محدود شده که نتوان اطلاعات کل جاده ها را نگه داشت.)** # ورودی در خط اول ورودی $n$ و $m$ که به ترتیب تعداد شهر ها و تعداد جاده‌ها است آمده. در خط بعدی به ترتیب ۴ عدد $x$ و $y$ و $z$ و $c$ آمده‌است. و در خط آخر ابتدا شماره شهری که مجید در آن است($start$) و سپس شماره شهری که شرکت سحاب در آن واقع شده($end$)، آمده است. $$2 \le n \le 100\ 000$$ $$0 \le m \le 10\ 000\ 000$$ $$0 \le x, y, z, c \le 1\ 000\ 000\ 000$$ $$0 \le start , end \le n-1$$ $$start \neq end$$ # خروجی در خط اول خروجی تعداد جاده ها برای رسیدن از شهر مجید به شهر شرکت سحاب را چاپ کنید و در خط بعدی به ترتیب شماره شهرهایی که مجید در این مسیر از آن‌ها می‌گذرد(همراه با شهر مبدا و مقصد) را چاپ کنید.(در صورتی که چندین مسیر مطلوب وجود داشت یکی از آن‌ها را به دلخواه چاپ کنید.) **مسیری که چاپ می‌کنید نباید شامل هیچ‌گونه دوری باشد، همچنین طول مسیری که به عنوان جواب چاپ می‌کنید باید کمتر از $n$ باشد.(تضمین می‌شود در صورت وجود جواب، مسیری وجود دارد که طول آن کمتر از $n$ باشد.)** در صورتی که مسیری برای رسیدن به شرکت سحاب وجود نداشت ```-1``` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 4 2 3 2 2 1 3 ``` ## خروجی نمونه ۱ ``` 1 1 3 ``` **توضیح نمونه‌ی ۱:** با توجه به الگوریتم *KISS* جاده‌ی‌ اول بین شهرهای ۲و۳، جاده‌ی دوم بین شهرهای ۰و۳، جاده‌ی سوم بین شهرهای ۱و۳ و جاده‌ی چهارم بین شهرهای ۱و۲ کشیده می‌شود. در نتیجه شکل نهایی جاده ها به صورت زیر خواهد بود. ![توضیح تصویر](https://www.dropbox.com/s/e5n7yrempdnsdjm/graph4.png?dl=1) ## ورودی نمونه ۲ ``` 100 99 8 97 46 1 90 77 ``` ## خروجی نمونه ۲ ``` 17 90 55 19 24 54 91 35 0 49 87 38 72 84 80 18 32 75 77 ```

مجید در راه سحاب

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۳۲ مگابایت

چند صباحی است که مجید به دنبال کار در شرکت‌های برنامه‌نویسی می‌گردد، اما شرکت‌های برنامه‌نویسی به دلایل نامعلومی او را رد می‌کنند .

امروز مجید تصمیم گرفته که شانس خود را برای شرکت سحاب امتحان کند، بدین منظور مجید رزومه خود را برای شرکت سحاب می‌فرستد.

بعد از بررسی رزومه مجید، شرکت سحاب متوجه می‌شود که این مجید همان مجید مشهور است و در نتیجه می‌خواهند که او را برای کار در شرکت نپذیرند، اما از آنجا که مسئولین استخدام شرکت سحاب انسان‌های مهربانی هستند، یک شانس به مجید می‌دهند و به اون می‌گویند در صورتی استخدام می‌شود که بتواند از یک مسیری به شرکت سحاب برسد و در این مسیر از هر شهری حداکثر یک بار عبور کند!

کشوری که مجید در آن زندگی می‌کند شامل $n$ شهر و $m$ جاده‌ی دو طرفه است، که شهرها از ۰ تا $n-1$ شماره‌گذاری شده‌اند ولی جاده‌های این کشور به طرز عجیبی طراحی شده‌اند.

جاده‌ها بطور کاملاً تصادفی کشیده شده‌اند! برای هرچه بیشتر تصادفی شدن این جاده‌کشی، از الگوریتم KISS (مخفف Keep It Simple Stupid) برای ساخت اعداد تصادفی و کشیدن جاده‌ها استفاده شده‌ است. کد این الگوریتم در زبان ++C به شکل زیر است. (مقادیر اولیه‌ی متغیرهای $x$ و $y$ و $z$ و $c$ در ورودی به شما داده ‌می‌شود.)

unsigned long long x, y, z, c;

unsigned long long uint32(unsigned long long i)
{
    return i & 0xFFFFFFFF;
}

unsigned long long kiss()
{
    x = uint32( 69069 * x + 12345 );

    y ^= uint32(y << 13);
    y ^= uint32(y >> 17);
    y ^= uint32(y << 5);

    unsigned long long t = 698769069 * z + c;
    c = uint32(t >> 32);
    z = uint32(t);

    return uint32(x + y + z);
}

سپس مسئولین بین شهر‌ها به صورت زیر جاده احداث کرده‌اند. (تابع build_road_between بین دو شهر یک جاده دوطرفه قرار می‌دهد.)

for (int i = 0; i < m; i++)
{
    int u = kiss() % n;
    int v = kiss() % n;
    build_road_between(u , v);
}

دقت کنید که ممکن است بین ۲ شهر بیش از یک جاده احداث شود و یا ممکن است از یک شهر به خودش جاده‌ای وجود داشته باشد.

با توجه به اینکه مجید به دلایل نامعلومی نمی‌تواند مسیر رسیدن به سحاب را پیدا کند، از شما کمک خواسته تا بلکه شما بتوانید به او برای رسیدن به این شرکت و این شغل کمک کنید.

(به محدودیت حافظه و ورودی‌های این سوال دقت کنید، حافظه به گونه‌ای محدود شده که نتوان اطلاعات کل جاده ها را نگه داشت.)

ورودی🔗

در خط اول ورودی $n$ و $m$ که به ترتیب تعداد شهر ها و تعداد جاده‌ها است آمده.

در خط بعدی به ترتیب ۴ عدد $x$ و $y$ و $z$ و $c$ آمده‌است.

و در خط آخر ابتدا شماره شهری که مجید در آن است( $start$ ) و سپس شماره شهری که شرکت سحاب در آن واقع شده( $end$ )، آمده است. $2 \le n \le 100\ 000$ $0 \le m \le 10\ 000\ 000$ $0 \le x, y, z, c \le 1\ 000\ 000\ 000$ $0 \le start , end \le n-1$ $start \neq end$

خروجی🔗

در خط اول خروجی تعداد جاده ها برای رسیدن از شهر مجید به شهر شرکت سحاب را چاپ کنید و در خط بعدی به ترتیب شماره شهرهایی که مجید در این مسیر از آن‌ها می‌گذرد(همراه با شهر مبدا و مقصد) را چاپ کنید.(در صورتی که چندین مسیر مطلوب وجود داشت یکی از آن‌ها را به دلخواه چاپ کنید.)

مسیری که چاپ می‌کنید نباید شامل هیچ‌گونه دوری باشد، همچنین طول مسیری که به عنوان جواب چاپ می‌کنید باید کمتر از $n$ باشد.(تضمین می‌شود در صورت وجود جواب، مسیری وجود دارد که طول آن کمتر از $n$ باشد.)

در صورتی که مسیری برای رسیدن به شرکت سحاب وجود نداشت -1 را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4 4
2 3 2 2
1 3

خروجی نمونه ۱🔗

1
1 3

توضیح نمونه‌ی ۱: با توجه به الگوریتم KISS جاده‌ی‌ اول بین شهرهای ۲و۳، جاده‌ی دوم بین شهرهای ۰و۳، جاده‌ی سوم بین شهرهای ۱و۳ و جاده‌ی چهارم بین شهرهای ۱و۲ کشیده می‌شود. در نتیجه شکل نهایی جاده ها به صورت زیر خواهد بود. توضیح تصویر

ورودی نمونه ۲🔗

100 99
8 97 46 1
90 77

خروجی نمونه ۲🔗

17
90 55 19 24 54 91 35 0 49 87 38 72 84 80 18 32 75 77

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مجید که به تازگی فهمیده در برنامه‌نویسی استعدادی ندارد، تصمیم گرفته به شغل شریف مزرعه داری مشغول شود. به همین علّت یک مزرعه خریده است و می‌خواهد در آن به کشت و کار بپردازد. محصولاتی که مجید قصد کاشت آن‌ها را دارد، سه نوع هستند: درختی(مثل گردو)، بوته‌ای(مثل تمشک)، ریشه‌ای(مثل هویج) مزرعه‌ از تعدادی زمین کشت تشکیل شده است که هر یک از آن‌ها قابلیت کشت تعدادی از سه نوع گیاه گفته شده را دارند. مثلا ممکن است در یک زمین فقط گیاه بوته‌ای بتوان کاشت، یا در زمینی دیگر گیاهان بوته‌ای و ریشه‌ای بتوان کاشت. ممکن است در یک زمین هیچ نوع گیاهی نیز نتوان کاشت. ابتدا تمام زمین‌های کشت عاری از هر گونه گیاه هستند. هر گیاه یک نرخ رشد(در واحد کیلوگرم) مثل $s$ دارد و هر گاه در یک زمینِ کشت، گیاهی کاشته شود، از همان روز به مدّت ۵ روز، روزانه $s$ کیلوگرم از محصولات آن گیاه، به انبار مزرعه اضافه خواهد شد. علاوه بر موارد گفته شده، در فروشگاه محصولات کشاورزی چند نوع کود وجود دارد. هر کود یک ضریب افزایندگی و یک میزان ماندگاری دارد. اگر کودی با ضریب افزایندگی $t$ و میزان ماندگاری $d$ روز به یکی از زمین‌های کشاورزی اضافه کنیم، از آن روز به مدّت $d$ روز، هر گیاهی که در آن زمین در حال ثمردهی باشد $t$ برابر ثمر خواهد داد. مثلا اگر گیاهی با نرخ رشد ۵ در آن زمین کاشته شده باشد و ما در سومین روزی که از کشت گیاه می‌گذرد به آن کودی با ضریب افزایندگی ۶ بدهیم، در آن روز و دو روز پس از آن گیاه ۳۰ کیلوگرم بار خواهد داد و باقی مانده عمرش را مثل قبل سپری خواهد کرد. لازم به ذکر است که در صورتی که در یک زمین چند نوع کود وجود داشته باشند، ضریب افزایندگی در آن زمین به اندازه‌ی مجموع ضریب افزایندگی آن کودها خواهد بود. مثلا اگر در روز اول کودی با ضریب افزایندگی ۴ و میزان ماندگاری ۴ روز به زمین اضافه کنیم، در روز دوم کودی با ضریب افزایندگی ۲ و میزان ماندگاری ۲ روز به زمین اضافه کنیم، در روز اول و چهارم گیاهان داخل زمین ۴ برابر و در روز دوم و سوم نیز ۶ برابر ثمر خواهند داد. علاوه بر این‌ها! هر روز تعدادی مشتری به مجید مراجعه می‌کنند تا محصولات او را بخرند. هر گیاه نیز یک قیمت پایه بر حسب «سکه بر کیلوگرم» دارد. چنان چه در انبار مزرعه‌ی مجید به اندازه‌ی تقاضای آن مشتری از آن محصول موجود باشد، درخواست مشتری پاسخ داده خواهد شد و متناسب با میزان خرید آن مشتری و نوع محصول خریداری شده، پول به مجید خواهد رسید. در غیر این صورت درخواست مشتری رد خواهد شد. مجید نزد هر مشتری مقداری آب‌رو دارد. هر بار که درخواست یک مشتری رد شود، آب‌روی مجید نزد آن مشتری یک واحد کم می‌شود، در غیر این صورت نیز یک واحد افزوده می‌شود. وقتی مشتری‌ای که آب‌روی مجید نزد آن $e$ است، از مجید محصولی با قیمت پایه $p$ می‌خرد، قیمت آن گیاه برای آن مشتری $p + e$ سکه بر کیلوگرم خواهد بود. دقّت کنید قیمت تمام شده‌ی یک محصول از صفر نمی‌تواند کم‌تر باشد و آب‌رویی که مجید نزد هر مشتری دارد در ابتدا صفر است. ما به ازای هر روز از دوران مزرعه‌داری مجید به شما تعدادی دستور و تعدادی پرسش می‌دهیم، شما باید به دستورها عمل کنید و جواب پرسش‌ها را به ترتیب در خروجی چاپ کنید. جزییات بیشتر در این مورد را در قسمت «ورودی» و «خروجی» بخوانید. # ورودی در خط اول ورودی، $n$ تعداد زمین‌های کشت را به شما می‌دهیم. در خط $i$ام از هر یک از $n$ خط بعد مشخصات زمین $i$ام می‌آید. مشخصات هر زمین تنها شامل سه عدد است که هر کدام ۰ یا ۱ هستند. عدد اول در صورتی ۱ است که بتوان در آن زمین گیاه درختی کاشت. عدد دوم در صورتی ۱ است که بتوان در آن زمین گیاه بوته‌ای کاشت. عدد سوم نیز در صورتی ۱ است که بتوان در آن زمین گیاه ریشه‌ای کاشت. سپس $m$ تعداد گیاهان داده می‌شود. در خط $i$ام از هر یک از $m$ خط بعد مشخصات گیاه $i$ام می‌آید. به ازای هر گیاه، ابتدا نام آن و سپس نوع آن داده می‌شود. نوع هر گیاه یک کلمه برابر یکی از سه کلمه‌ی `risheh` و `derakht` و `buteh` است. بعد از یک فاصله قیمت پایه‌ی آن گیاه و بعد از یک فاصله‌ی دیگر نیز ضریب رشد آن گیاه داده می‌شود. سپس $k$ تعداد کودها داده می‌شود. در خط $i$ام از هر یک از $k$ خط بعد، مشخصات کود $i$ام می‌آید. ابتدا نوع آن کود(یک کلمه)، سپس ضریب افزایندگی و سپس میزان ماندگاری آن کود داده می‌شوند. در خط بعد عدد $d$ داده می‌شود که برابر تعداد روزها است. در ادامه $d$ دسته از دستورها و پرسش‌ها داده می‌شود. دسته‌ی $i$ام پرسش‌ها و دستورهایی است که در روز $i$ام مجید به شما می‌دهد. در هر دسته، ابتدا عددی مثل $q_1$تعداد دستورها داده می‌شود. در هر یک $q_1$ خط بعدی، دستوراتی از انواع زیر داده می‌شود: `bekar zamin_id giyah_name` این دستور به این معنی است که در زمین شماره `zamin_id` گیاهی به اسم `giyah_name` بکارید. در صورتی که در این روز گیاهی در آن زمین باشد که عمرش هنوز تمام نشده باشد، این دستور را نادیده می‌گیریم. `kooddehi zamin_id kood_name` به این معنی است که به زمین `zamin_id` یک واحد از کود `kood_name` را اضافه کنیم. `koodgiri kood_name value` به این معنی است که `value` واحد از کود نوع `kood_name` به دست ما رسیده است. این مقدار را در انبار ذخیره می‌کنیم! چنان چه هر یک از عملیات بالا با موفقیت انجام شد باید به ازای آن دستور عبارت `done` را چاپ کنید. در غیر این صورت باید عبارت `failed` را چاپ کنید. پس از دریافت $q_1$ دستور، عدد $q_2$ آمده‌است و از شما $q_2$ پرسش صورت می‌گیرد. پرسش‌ها در پایان روز انجام می‌گیرند، یعنی در هنگام پاسخ دادن به پرسش‌ها، فرض می‌کنیم که روز به پایان رسیده است و تمام محصولات تولید شده از زمین‌های کشت به انبار منتقل شده‌اند. `moshtari giyah_name value` به این معنی است که مشتری‌ای به اسم `moshtari` درخواست داده است به او `value` کیلوگرم از محصول `giyah_name` بفروشیم. اگر قادر به انجام این کار بودیم، تعداد سکّه‌ای که از مشتری دریافت می‌شود را چاپ کنید. در غیر این صورت `-1` چاپ کنید. در پایان هر روز باید لیست (حداکثر) ۵ مشتری که بیشترین خرید را از مزرعه داشته‌اند به ترتیب چاپ کنید. در صورتی که دو مشتری به یک اندازه خرید از فروشگاه داشته باشند (بر حسب سکه) کسی که نامش از نظر الفبایی کوچک‌تر است، ارجحیت دارد. توجه کنید که در صورتی که در درخواست‌های مشتریان، دو مشتری با یک اسم ظاهر شوند، آن دو یک نفر هستند! یعنی به طور مثال دو مشتری مختلف با اسم `ali` وجود ندارند. هم‌چنین اگر اوّلین مشتری در روز $i$ام به ما مراجعه کند، تا قبل از آن روز لیست پرسودترین ۵ مشتری را چاپ نمی‌کنیم! **لازم به ذکر است که در یک روز دستورات و پرسش‌ها به ترتیب زمانی به ما داده می‌شوند.** **در ضمن تمام اعداد ورودی حداکثر برابر ۱۰ هستند و تمام کلمات ورودی فقط از حروف کوچک الفبای انگلیسی تشکیل شده‌اند.** # خروجی به ازای هر پرسش در هر خط جواب آن پرسش را چاپ کنید. پس از پرسش‌های هر روز نیز در یک خط نام (حداکثر) ۵ پرسودترین مشتری را چاپ کنید. (به ترتیب از بیشترین خرید به کمترین خرید) # مثال ## ورودی نمونه ۱ ``` 1 1 1 1 1 havij risheh 10 10 0 1 1 bekar 1 havij 1 havijman havij 9 ``` ## خروجی نمونه ۱ ``` done 90 havijman ``` ## ورودی نمونه ۲ ``` 7 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 3 havij risheh 10 10 gerdoo derakht 5 5 talebi buteh 2 1 2 koodone 3 2 koodtwo 3 4 6 10 bekar 1 havij bekar 2 havij bekar 3 havij kooddehi 2 koodone koodgiri koodone 3 koodgiri koodtwo 2 kooddehi 1 koodone kooddehi 1 koodtwo bekar 4 gerdoo bekar 6 talebi 0 0 10 havijkhar havij 8 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 9 havijkhar havij 1 akbar talebi 2 akbar havij 5 0 2 rostam gerdoo 10 rostam gerdoo 5 1 kooddehi 4 koodone 1 mohsen talebi 5 0 1 akbar talebi 1 0 10 akbar talebi 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 havijkhar havij 10 ``` ## خروجی نمونه ۲ ``` done failed done failed done done done done done done 80 110 120 130 140 150 144 17 4 55 havijkhar akbar 50 30 havijkhar rostam akbar done -1 havijkhar rostam akbar mohsen 4 havijkhar rostam akbar mohsen -1 180 190 200 210 220 230 240 250 260 havijkhar rostam akbar mohsen ```

مجید، رییس مزرعه

محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

مجید که به تازگی فهمیده در برنامه‌نویسی استعدادی ندارد، تصمیم گرفته به شغل شریف مزرعه داری مشغول شود. به همین علّت یک مزرعه خریده است و می‌خواهد در آن به کشت و کار بپردازد.

محصولاتی که مجید قصد کاشت آن‌ها را دارد، سه نوع هستند: درختی(مثل گردو)، بوته‌ای(مثل تمشک)، ریشه‌ای(مثل هویج)

مزرعه‌ از تعدادی زمین کشت تشکیل شده است که هر یک از آن‌ها قابلیت کشت تعدادی از سه نوع گیاه گفته شده را دارند. مثلا ممکن است در یک زمین فقط گیاه بوته‌ای بتوان کاشت، یا در زمینی دیگر گیاهان بوته‌ای و ریشه‌ای بتوان کاشت. ممکن است در یک زمین هیچ نوع گیاهی نیز نتوان کاشت.

ابتدا تمام زمین‌های کشت عاری از هر گونه گیاه هستند. هر گیاه یک نرخ رشد(در واحد کیلوگرم) مثل $s$ دارد و هر گاه در یک زمینِ کشت، گیاهی کاشته شود، از همان روز به مدّت ۵ روز، روزانه $s$ کیلوگرم از محصولات آن گیاه، به انبار مزرعه اضافه خواهد شد.

علاوه بر موارد گفته شده، در فروشگاه محصولات کشاورزی چند نوع کود وجود دارد. هر کود یک ضریب افزایندگی و یک میزان ماندگاری دارد. اگر کودی با ضریب افزایندگی $t$ و میزان ماندگاری $d$ روز به یکی از زمین‌های کشاورزی اضافه کنیم، از آن روز به مدّت $d$ روز، هر گیاهی که در آن زمین در حال ثمردهی باشد $t$ برابر ثمر خواهد داد. مثلا اگر گیاهی با نرخ رشد ۵ در آن زمین کاشته شده باشد و ما در سومین روزی که از کشت گیاه می‌گذرد به آن کودی با ضریب افزایندگی ۶ بدهیم، در آن روز و دو روز پس از آن گیاه ۳۰ کیلوگرم بار خواهد داد و باقی مانده عمرش را مثل قبل سپری خواهد کرد.

لازم به ذکر است که در صورتی که در یک زمین چند نوع کود وجود داشته باشند، ضریب افزایندگی در آن زمین به اندازه‌ی مجموع ضریب افزایندگی آن کودها خواهد بود. مثلا اگر در روز اول کودی با ضریب افزایندگی ۴ و میزان ماندگاری ۴ روز به زمین اضافه کنیم، در روز دوم کودی با ضریب افزایندگی ۲ و میزان ماندگاری ۲ روز به زمین اضافه کنیم، در روز اول و چهارم گیاهان داخل زمین ۴ برابر و در روز دوم و سوم نیز ۶ برابر ثمر خواهند داد.

علاوه بر این‌ها! هر روز تعدادی مشتری به مجید مراجعه می‌کنند تا محصولات او را بخرند. هر گیاه نیز یک قیمت پایه بر حسب «سکه بر کیلوگرم» دارد. چنان چه در انبار مزرعه‌ی مجید به اندازه‌ی تقاضای آن مشتری از آن محصول موجود باشد، درخواست مشتری پاسخ داده خواهد شد و متناسب با میزان خرید آن مشتری و نوع محصول خریداری شده، پول به مجید خواهد رسید. در غیر این صورت درخواست مشتری رد خواهد شد.

مجید نزد هر مشتری مقداری آب‌رو دارد. هر بار که درخواست یک مشتری رد شود، آب‌روی مجید نزد آن مشتری یک واحد کم می‌شود، در غیر این صورت نیز یک واحد افزوده می‌شود. وقتی مشتری‌ای که آب‌روی مجید نزد آن $e$ است، از مجید محصولی با قیمت پایه $p$ می‌خرد، قیمت آن گیاه برای آن مشتری $p + e$ سکه بر کیلوگرم خواهد بود. دقّت کنید قیمت تمام شده‌ی یک محصول از صفر نمی‌تواند کم‌تر باشد و آب‌رویی که مجید نزد هر مشتری دارد در ابتدا صفر است.

ما به ازای هر روز از دوران مزرعه‌داری مجید به شما تعدادی دستور و تعدادی پرسش می‌دهیم، شما باید به دستورها عمل کنید و جواب پرسش‌ها را به ترتیب در خروجی چاپ کنید. جزییات بیشتر در این مورد را در قسمت «ورودی» و «خروجی» بخوانید.

ورودی🔗

در خط اول ورودی، $n$ تعداد زمین‌های کشت را به شما می‌دهیم.

در خط $i$ ام از هر یک از $n$ خط بعد مشخصات زمین $i$ ام می‌آید. مشخصات هر زمین تنها شامل سه عدد است که هر کدام ۰ یا ۱ هستند. عدد اول در صورتی ۱ است که بتوان در آن زمین گیاه درختی کاشت. عدد دوم در صورتی ۱ است که بتوان در آن زمین گیاه بوته‌ای کاشت. عدد سوم نیز در صورتی ۱ است که بتوان در آن زمین گیاه ریشه‌ای کاشت.

سپس $m$ تعداد گیاهان داده می‌شود.

در خط $i$ ام از هر یک از $m$ خط بعد مشخصات گیاه $i$ ام می‌آید. به ازای هر گیاه، ابتدا نام آن و سپس نوع آن داده می‌شود. نوع هر گیاه یک کلمه برابر یکی از سه کلمه‌ی risheh و derakht و buteh است. بعد از یک فاصله قیمت پایه‌ی آن گیاه و بعد از یک فاصله‌ی دیگر نیز ضریب رشد آن گیاه داده می‌شود.

سپس $k$ تعداد کودها داده می‌شود.

در خط $i$ ام از هر یک از $k$ خط بعد، مشخصات کود $i$ ام می‌آید. ابتدا نوع آن کود(یک کلمه)، سپس ضریب افزایندگی و سپس میزان ماندگاری آن کود داده می‌شوند.

در خط بعد عدد $d$ داده می‌شود که برابر تعداد روزها است. در ادامه $d$ دسته از دستورها و پرسش‌ها داده می‌شود. دسته‌ی $i$ ام پرسش‌ها و دستورهایی است که در روز $i$ ام مجید به شما می‌دهد.

در هر دسته، ابتدا عددی مثل $q_1$ تعداد دستورها داده می‌شود.

در هر یک $q_1$ خط بعدی، دستوراتی از انواع زیر داده می‌شود:

bekar zamin_id giyah_name

این دستور به این معنی است که در زمین شماره zamin_id گیاهی به اسم giyah_name بکارید. در صورتی که در این روز گیاهی در آن زمین باشد که عمرش هنوز تمام نشده باشد، این دستور را نادیده می‌گیریم.

kooddehi zamin_id kood_name

به این معنی است که به زمین zamin_id یک واحد از کود kood_name را اضافه کنیم.

koodgiri kood_name value

به این معنی است که value واحد از کود نوع kood_name به دست ما رسیده است. این مقدار را در انبار ذخیره می‌کنیم!

چنان چه هر یک از عملیات بالا با موفقیت انجام شد باید به ازای آن دستور عبارت done را چاپ کنید. در غیر این صورت باید عبارت failed را چاپ کنید.

پس از دریافت $q_1$ دستور، عدد $q_2$ آمده‌است و از شما $q_2$ پرسش صورت می‌گیرد. پرسش‌ها در پایان روز انجام می‌گیرند، یعنی در هنگام پاسخ دادن به پرسش‌ها، فرض می‌کنیم که روز به پایان رسیده است و تمام محصولات تولید شده از زمین‌های کشت به انبار منتقل شده‌اند.

moshtari giyah_name value

به این معنی است که مشتری‌ای به اسم moshtari درخواست داده است به او value کیلوگرم از محصول giyah_name بفروشیم. اگر قادر به انجام این کار بودیم، تعداد سکّه‌ای که از مشتری دریافت می‌شود را چاپ کنید. در غیر این صورت -1 چاپ کنید.

در پایان هر روز باید لیست (حداکثر) ۵ مشتری که بیشترین خرید را از مزرعه داشته‌اند به ترتیب چاپ کنید. در صورتی که دو مشتری به یک اندازه خرید از فروشگاه داشته باشند (بر حسب سکه) کسی که نامش از نظر الفبایی کوچک‌تر است، ارجحیت دارد.

توجه کنید که در صورتی که در درخواست‌های مشتریان، دو مشتری با یک اسم ظاهر شوند، آن دو یک نفر هستند! یعنی به طور مثال دو مشتری مختلف با اسم ali وجود ندارند. هم‌چنین اگر اوّلین مشتری در روز $i$ ام به ما مراجعه کند، تا قبل از آن روز لیست پرسودترین ۵ مشتری را چاپ نمی‌کنیم!

لازم به ذکر است که در یک روز دستورات و پرسش‌ها به ترتیب زمانی به ما داده می‌شوند.

در ضمن تمام اعداد ورودی حداکثر برابر ۱۰ هستند و تمام کلمات ورودی فقط از حروف کوچک الفبای انگلیسی تشکیل شده‌اند.

خروجی🔗

به ازای هر پرسش در هر خط جواب آن پرسش را چاپ کنید.

پس از پرسش‌های هر روز نیز در یک خط نام (حداکثر) ۵ پرسودترین مشتری را چاپ کنید. (به ترتیب از بیشترین خرید به کمترین خرید)

مثال🔗

ورودی نمونه ۱🔗

1
1 1 1
1
havij risheh 10 10
0
1
1
bekar 1 havij
1
havijman havij 9

خروجی نمونه ۱🔗

done
90
havijman

ورودی نمونه ۲🔗

7
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
3
havij risheh 10 10
gerdoo derakht 5 5
talebi buteh 2 1
2
koodone 3 2
koodtwo 3 4
6
10
bekar 1 havij
bekar 2 havij
bekar 3 havij
kooddehi 2 koodone
koodgiri koodone 3
koodgiri koodtwo 2
kooddehi 1 koodone
kooddehi 1 koodtwo
bekar 4 gerdoo
bekar 6 talebi
0
0
10
havijkhar havij 8
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 9
havijkhar havij 1
akbar talebi 2
akbar havij 5
0
2
rostam gerdoo 10
rostam gerdoo 5
1
kooddehi 4 koodone
1
mohsen talebi 5
0
1
akbar talebi 1
0
10
akbar talebi 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10

خروجی نمونه ۲🔗

done
failed
done
failed
done
done
done
done
done
done
80
110
120
130
140
150
144
17
4
55
havijkhar akbar
50
30
havijkhar rostam akbar
done
-1
havijkhar rostam akbar mohsen
4
havijkhar rostam akbar mohsen
-1
180
190
200
210
220
230
240
250
260
havijkhar rostam akbar mohsen

+ محدودیت زمان: ۶ ثانیه + **محدودیت حافظه: ۳۲ مگابایت** ---------- مجید که از کار در مزرعه خسته شده است، به هنر آشپزی روی آورده و می‌خواهد سبک جدیدی از آشپزی را ارائه بدهد. به این منظور او با استفاده از فرمول‌های پیچیده‌ای که دارد تعدادی غذا درست می‌کند و هر غذا از تعدادی ماده‌ی اولیه درست می‌شود. مواد‌ اولیه را با اعداد صحیح بین ۰ تا $10^9$ نشان می‌دهیم و تعداد غذاهایی که مجید می‌پزد را با $n$ مشخص می‌کنیم. مجید در آشپزی هم رفتارهای عجیبی دارد! مثلاً همه‌ی غذاهایی که مجید می‌پزد تعداد مواد اولیه‌شان برابر است. تعداد مواد اولیه‌ی غذاهای مجید را با $m$ مشخص می‌کنیم. همچنین هر غذایی یک دستور پخت دارد که مشخص می‌کند مواد اولیه به چه ترتیبی باید اضافه شوند؛ یعنی می‌توان گفت به ازای غذای $j$ام، مجید دنباله‌ای از مواد اولیه $a_{j, 1}, a_{j, 2}, a_{j, 3}, ..., a_{j, m}$ دارد که شماره مواد اولیه‌ی آن و ترتیب اضافه شدن آن‌ها را مشخص می‌کند. ($1 \le j \le n$) عجیب‌ترین رفتار مجید در آشپزی این است که تعداد غذاهایی که می‌پزد خیلی زیاد است! **آنقدر زیاد است که در حافظه نمی‌گنجد** و نمی‌تواند بطور مستقیم دستور پخت آن غذاها را به فرد دیگری توضیح دهد؛ برای همین دنباله‌ی مواد اولیه‌ی غذاهای خود را کاملاً اتفاقی می‌سازد! برای این کار از الگوریتم *KISS* (مخفف *Keep It Simple Stupid*)استفاده می‌کند. کد این الگوریتم در زبان ++C به شکل زیر است. (مقادیر اولیه‌ی متغیرهای $x$ و $y$ و $z$ و $c$ در ورودی به شما داده ‌می‌شود.) ```c++ unsigned long long x, y, z, c; unsigned long long uint32(unsigned long long i) { return i & 0xFFFFFFFF; } unsigned long long kiss() { x = uint32( 69069 * x + 12345 ); y ^= uint32(y << 13); y ^= uint32(y >> 17); y ^= uint32(y << 5); unsigned long long t = 698769069 * z + c; c = uint32(t >> 32); z = uint32(t); return uint32(x + y + z); } ``` سپس مجید بصورت کد زیر، دستور پخت غذاها را تولید می‌کند. (مقدار $e$ نیز در ورودی مسئله آمده است.) ```c++ for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) a[i][j] = kiss() % e; ``` مجید پس از مدتی طولانی متوجه شد که با اینکه دستور پخت‌هایش بصورت کاملاً اتفاقی و پخش هستند، ولی ممکن است تعدادی از این غذاها عیناً یکسان باشند؛ یعنی تمام مواد اولیه و ترتیب اضافه کردنشان داخل دستور پخت یکی باشد. (دقت کنید که تعداد مواد اولیه در دستور پخت غذاها هم برابر است.) حال مجید از شما می‌خواهد برنامه‌ای بنویسید که با ورودی گرفتن همه‌ی اطلاعات، تعداد انواع غذاهای مختلفی را که تولید می‌کند **بصورت تقریبی** را خروجی دهد. برای چالش‌برانگیزتر شدن مسئله مجید اطلاعات چند روز مختلفش را به برنامه‌ی شما می‌دهد که چندین سناریوی مختلف تولید می‌کنند و شما باید به همه‌ی آن‌ها پاسخ بدید. (به بخش ورودی توجه کنید.) **البته نیازی نیست شما پاسخ دقیق را خروجی دهید؛ شما می‌توانید با کمی خطا پاسخ مسئله را بیابید. هرچه خروجی شما دقیق‌تر باشد، در نهایت نمره‌ای که برنامه‌ی شما از این سوال دریافت می‌کند بیشتر خواهد بود.** # ورودی در خط اول ورودی $t$ آمده که نمایانگر تعداد روزهایی است که مجید آشپزی می‌کند. به ازای هر روز، دو خط ورودی آمده. در خط اول روز $i$ام، ورودی ابتدا $n$ و سپس $m$ آمده است که تعداد غذاهای آن روز و تعداد مواد اولیه استفاده شده در هریک از آن غذاها را مشخص می‌کند. سپس در خط بعدی ورودی هر روز، به ترتیب ۵ عدد $x$ و $y$ و $z$ و $c$ و $e$ برای آن روز آمده است که نمایانگر مقادیر اولیه‌ی تابع تصادفی مورد استفاده‌ی مجید برای آن روز هستند. $$1 \le t \le 3$$ $$1 \le n \le 20\ 000\ 000$$ $$1 \le m \le 3$$ $$0 \le x , y , z , c \le 1\ 000\ 000\ 000$$ $$1 \le e \le 1\ 000\ 000\ 000$$ مجموع $n \times m$ برای همه‌ی $t$ روز حداکثر برابر $20\ 000\ 000$ است. # خروجی خروجی باید شامل $t$ خط باشد و در خط $i$ام تقریب‌تان از تعداد غذاهای متمایزی که مجید در روز $i$ام درست می‌کند را چاپ خواهید کرد. # مثال ## ورودی نمونه ``` 3 10 1 1 2 3 4 10 10 2 1 2 3 4 10 10 3 4 3 2 1 3 ``` ## خروجی نمونه ``` 7 9 7 ``` **توضیح ورودی نمونه : ** در این مثال مجید ۳ روز آشپزی خواهد کرد که اطلاعات هر روز در ۲ خط متوالی آمده است. در خط دوم و سوم ورودی اطلاعات روز اول آشپزی، در خط چهارم و پنجم ورودی اطلاعات روز دوم آشپزی و در ۲ خط آخر اطلاعات روز سوم آشپزی آمده است.

مجید و هنر آشپزی

محدودیت زمان: ۶ ثانیه
محدودیت حافظه: ۳۲ مگابایت

مجید که از کار در مزرعه خسته شده است، به هنر آشپزی روی آورده و می‌خواهد سبک جدیدی از آشپزی را ارائه بدهد. به این منظور او با استفاده از فرمول‌های پیچیده‌ای که دارد تعدادی غذا درست می‌کند و هر غذا از تعدادی ماده‌ی اولیه درست می‌شود. مواد‌ اولیه را با اعداد صحیح بین ۰ تا $10^9$ نشان می‌دهیم و تعداد غذاهایی که مجید می‌پزد را با $n$ مشخص می‌کنیم.

مجید در آشپزی هم رفتارهای عجیبی دارد! مثلاً همه‌ی غذاهایی که مجید می‌پزد تعداد مواد اولیه‌شان برابر است. تعداد مواد اولیه‌ی غذاهای مجید را با $m$ مشخص می‌کنیم. همچنین هر غذایی یک دستور پخت دارد که مشخص می‌کند مواد اولیه به چه ترتیبی باید اضافه شوند؛ یعنی می‌توان گفت به ازای غذای $j$ ام، مجید دنباله‌ای از مواد اولیه $a_{j, 1}, a_{j, 2}, a_{j, 3}, ..., a_{j, m}$ دارد که شماره مواد اولیه‌ی آن و ترتیب اضافه شدن آن‌ها را مشخص می‌کند. ( $1 \le j \le n$ )

عجیب‌ترین رفتار مجید در آشپزی این است که تعداد غذاهایی که می‌پزد خیلی زیاد است! آنقدر زیاد است که در حافظه نمی‌گنجد و نمی‌تواند بطور مستقیم دستور پخت آن غذاها را به فرد دیگری توضیح دهد؛ برای همین دنباله‌ی مواد اولیه‌ی غذاهای خود را کاملاً اتفاقی می‌سازد! برای این کار از الگوریتم KISS (مخفف Keep It Simple Stupid)استفاده می‌کند. کد این الگوریتم در زبان ++C به شکل زیر است. (مقادیر اولیه‌ی متغیرهای $x$ و $y$ و $z$ و $c$ در ورودی به شما داده ‌می‌شود.)

unsigned long long x, y, z, c;

unsigned long long uint32(unsigned long long i)
{
    return i & 0xFFFFFFFF;
}

unsigned long long kiss()
{
    x = uint32( 69069 * x + 12345 );

    y ^= uint32(y << 13);
    y ^= uint32(y >> 17);
    y ^= uint32(y << 5);

    unsigned long long t = 698769069 * z + c;
    c = uint32(t >> 32);
    z = uint32(t);

    return uint32(x + y + z);
}

سپس مجید بصورت کد زیر، دستور پخت غذاها را تولید می‌کند. (مقدار $e$ نیز در ورودی مسئله آمده است.)

for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
        a[i][j] = kiss() % e;

مجید پس از مدتی طولانی متوجه شد که با اینکه دستور پخت‌هایش بصورت کاملاً اتفاقی و پخش هستند، ولی ممکن است تعدادی از این غذاها عیناً یکسان باشند؛ یعنی تمام مواد اولیه و ترتیب اضافه کردنشان داخل دستور پخت یکی باشد. (دقت کنید که تعداد مواد اولیه در دستور پخت غذاها هم برابر است.)

حال مجید از شما می‌خواهد برنامه‌ای بنویسید که با ورودی گرفتن همه‌ی اطلاعات، تعداد انواع غذاهای مختلفی را که تولید می‌کند بصورت تقریبی را خروجی دهد. برای چالش‌برانگیزتر شدن مسئله مجید اطلاعات چند روز مختلفش را به برنامه‌ی شما می‌دهد که چندین سناریوی مختلف تولید می‌کنند و شما باید به همه‌ی آن‌ها پاسخ بدید. (به بخش ورودی توجه کنید.)

البته نیازی نیست شما پاسخ دقیق را خروجی دهید؛ شما می‌توانید با کمی خطا پاسخ مسئله را بیابید. هرچه خروجی شما دقیق‌تر باشد، در نهایت نمره‌ای که برنامه‌ی شما از این سوال دریافت می‌کند بیشتر خواهد بود.

ورودی🔗

در خط اول ورودی $t$ آمده که نمایانگر تعداد روزهایی است که مجید آشپزی می‌کند.

به ازای هر روز، دو خط ورودی آمده.

در خط اول روز $i$ ام، ورودی ابتدا $n$ و سپس $m$ آمده است که تعداد غذاهای آن روز و تعداد مواد اولیه استفاده شده در هریک از آن غذاها را مشخص می‌کند.

سپس در خط بعدی ورودی هر روز، به ترتیب ۵ عدد $x$ و $y$ و $z$ و $c$ و $e$ برای آن روز آمده است که نمایانگر مقادیر اولیه‌ی تابع تصادفی مورد استفاده‌ی مجید برای آن روز هستند.

$1 \le t \le 3$ $1 \le n \le 20\ 000\ 000$ $1 \le m \le 3$ $0 \le x , y , z , c \le 1\ 000\ 000\ 000$ $1 \le e \le 1\ 000\ 000\ 000$

مجموع $n \times m$ برای همه‌ی $t$ روز حداکثر برابر $20\ 000\ 000$ است.

خروجی🔗

خروجی باید شامل $t$ خط باشد و در خط $i$ ام تقریب‌تان از تعداد غذاهای متمایزی که مجید در روز $i$ ام درست می‌کند را چاپ خواهید کرد.

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

7
9
7

*توضیح ورودی نمونه : * در این مثال مجید ۳ روز آشپزی خواهد کرد که اطلاعات هر روز در ۲ خط متوالی آمده است. در خط دوم و سوم ورودی اطلاعات روز اول آشپزی، در خط چهارم و پنجم ورودی اطلاعات روز دوم آشپزی و در ۲ خط آخر اطلاعات روز سوم آشپزی آمده است.