+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، میخواهد کیبورد بخرد. کیبورد مورد نظر او به صورت یک مستطیل $n \times m$ است. به دلیل مشکلات اقتصادی او مجبور است که کیبورد دسته دومی خریداری کند که $k$ کلید آن خراب است. پروفسور باقر به دلیل ناشی بودنش فقط وقتی میتواند از کیبورد استفاده کند که فرد تا از کلیدهایش خراب باشند. برای همین تصمیم میگیرد تعدادی از کلیدهایش را خراب کند. به او کمک کنید با خراب کردن کمترین تعداد کلید به هدفش برسد. (و یا بگویید که این کار امکان ندارد) # ورودی سطر اول ورودی شامل سه عدد $n$ و $m$ و $k$ است که به ترتیب نشان دهنده‌ ی تعداد سطرها و ستون های کیبورد و تعداد کلیدهای خراب اند. در هریک از $k$ سطر بعدی، مختصات یک کلید خراب بصورت $r\ c$ آمده است که یعنی کلید در سطر $r$ام و ستون $c$ام کیبورد، خراب است. $$ 1 \le m,n,k \le 1000$$$$ 1 \le r \le n$$ $$ 1 \le c \le m$$ مختصات‌های داده شده متفاوتند. # خروجی اگر نمیتوان به پروفسور باقر کمک کرد (یعنی هیچ روشی برای خراب کردن تعدادی کلید سالم وجود ندارد که در نهایت تعداد فردی کلید‌ خراب باشند) $-1$ وگرنه در سطر اول $a$،تعداد کلیدهایی که باید خراب شوند، و در $a$ سطر بعد جایگاه کلید های خراب را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 3 2 1 1 2 3 ``` ## خروجی نمونه ۱ ``` 1 1 2 ``` ## ورودی نمونه ۲ ``` 2 2 3 2 2 1 1 2 1 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 2 2 4 2 2 1 1 2 1 1 2 ``` ## خروجی نمونه ۳ ``` -1 ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، به سراغ ماشین حسابش رفته است. بر روی ماشین حساب او ابتدا عدد ۱ نوشته شده است. او از آنجایی که ناشی است، تنها دو کار میتواند انجام دهد: یا عدد نوشته‌شده بر روی ماشین حساب را در ۵ ضرب میکند و یا عدد نوشته‌شده بر روی ماشین حساب را بر ۲ تقسیم می‌کند. سپس عدد نوشته‌شده بر روی ماشین حساب را می‌خواند. چون ناشی است از شما خواسته‌است که با دریافت عملیات‌های انجام شده، عدد نهایی نمایش داده‌شده روی ماشین‌ حسابش را بصورت خوانا به او بدهید. عددی برای پروفسور خوانا است که به صورت $a^b \times 10^c$ باشد که در آن $a$ عددی طبیعی و $b,c$ اعدادی صحیح باشند و شرایط زیر برقرار باشد: $$ -10^9 \le b,c \le 10^9$$ $$1 \le a \le 10^9$$ # ورودی سطر اول ورودی شامل عدد $n$ است که نمایانگر تعداد عملیات‌هایی است که پروفسور انجام داده است. در هریک از $n$ سطر بعدی یک عدد آمده که نمایانگر کاری است که پروفسور انجام می‌دهد. اگر این عدد ۲ باشد به معنای این است که پروفسور عدد نوشته‌شده روی ماشین حساب را بر ۲ تقسیم کرده است و اگر این عدد ۵ باشد به معنای این است که پروفسور عدد نوشته‌شده روی ماشین حساب را در ۵ ضرب کرده است. $$ 1 \le n \le 10\ 000 $$ # خروجی تنها سطر خروجی باید شامل سه عدد $a,b,c$ باشد که اعدادی صحیح هستند و: $$1 \le a \le 10^9 $$$$-10^9 \le b,c \le 10^9 $$ # مثال ## ورودی نمونه ۱ ``` 2 5 2 ``` ## خروجی نمونه ۱ ``` 5 2 -1 ``` ## ورودی نمونه ۲ ``` 2 5 5 ``` ## خروجی نمونه ۲ ``` 25 1 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، به دلیل کمبود بودجه‌اش،در قنادی به کار مشغول شده است. او مسئول بریدن و تقسیم کردن کیک‌ها و شیرینی‌ها است. روزی ز سر سنگ مشتری‌ای داخل قنادی می‌شود و کیکی سفارش می‌دهد و از پروفسور درخواست می‌کند که آن کیک را برای $k$ نفر برش دهد. یعنی جوری کیک را تکه تکه کند که در آخر مشتری بتواند به هر نفر از $k$ نفر تعدادی تکه کیک بدهد جوری که در آخر به هر نفر به اندازه‌ی برابر کیک رسیده باشد. یعنی به هر نفر باید دقیقا $\frac 1 k$ از کیک برسد.تنها نکته‌ای که این وسط وجود دارد این است که طبق قوانین قنادی، در هر بار برش پروفسور فقط می‌تواند یک تکه از کیک را دقیقا به $d$ تکه‌ی برابر تقسیم کند. حالا مشکلی که برای پروفسور پیش آمده این است که پروفسور (برای صرفه جویی در کارش) دنبال کوچکترین $d$ می‌گردد که با آن بتوان کیک را به طور مساوی بین $k$ نفر تقسیم کرد. شما این کوچکترین $d$ را به او بگویید. برای مثال فرض کنید که $k=4$ و $d=8$: پروفسور باقر میتواند کیک را به $8$ تکه تقسیم کند و مشتری می‌تواند به هر کدام از $4$ نفر دو تکه بدهد، یا پروفسور اول کیک را به $8$ تکه تقسیم کند و سپس دوباره هر تکه ایجاد شده را به $8$ تکه تقسیم کند و مشتری به هر نفر $16$ تکه بدهد تا به هر نفر به اندازه‌ی برابر کیک رسیده باشد. دوباره برای مثال اگر $k=2$، $d$ نمیتواند برابر 3 باشد. و باز برای مثال اگر $d$ برابر $k$ باشد، می‌توان کیک را به طور مساوی بین $k$ نفر تقسیم کرد. # ورودی در سطر اول ورودی عدد $k$ آمده است که نمایانگر تعداد افرادی است که کیک باید بین آنها به طور مساوی تقسیم شود. $$ 2 \le k \le 1\ 000\ 000 $$ # خروجی تنها سطر خروجی باید شامل کوچکترین عدد $d$ باشد که می‌توان با آن کیک را بین $k$ نفر به طور مساوی تقسیم کرد. # مثال ## ورودی نمونه ۱ ``` 2 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 12 ``` ## خروجی نمونه ۲ ``` 6 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، توسط یک مدیرِ منابعِ انسانیِ فروشگاهِ زنجیره‌ایِ ناشی‌تر، مسئولیت داده‌ شده است تا نیاز‌های فروشگاه را از کارخانه‌ها خریداری کند. او باید $m$ جنس را خریداری کند. اجناس را از ۱ تا $m$ شماره‌گذاری میکنیم. $n$ کارخانه وجود دارند(که آنها را از ۱ تا $n$ شماره‌گذاری می‌کنیم.) که هر کدام تمام این $m$ کالا را دارند اما قیمت هایشان برای هر کدام متفاوت است. قیمت کارخانه‌ی $i$ برای جنس $j$، $a_{i,j}$ است. به پروفسور باقر یک پرایدوانت داده‌ شده‌است تا با آنها اجناس را خریداری کند. او الان در فروشگاه است. هر کارخانه تا فروشگاه به اندازه ای فاصله دارد که هزینه بنزین رفت و برگشت $d_i$ است. حالا پروفسور(به علت ناشی بودن) از شما می‌خواهد که به او بگویید که کمینه‌ی هزینه برای خرید این اجناس چقدر است. فقط به این نکته دقت داشته باشید که وقتی پروفسور از فروشگاه به یک کارخانه می‌رود و اجناسی را از آنجا خریداری می‌کند،‌ برای اینکه قاطی نکند که هر جنس را از کدام کارخانه خریده‌است، بلافاصله به فروشگاه برمی‌گردد و اجناس را تحویل می‌دهد و سپس به دنبال اجناس دیگر می‌رود. # ورودی سطر اول ورودی شامل دو عدد $n$ و $m$ است که به ترتیب نمایانگر تعداد کارخانه‌ها و تعداد اجناس است. سپس در $i$امین سطر از هریک از $n$ سطر بعدی: ابتدا $d_i$ آمده‌است که نمایانگر هزینه‌ی بنزین رفت و برگشت از فروشگاه به کارخانه‌ی $i$ ام است. بعد از آن $m$ عدد آمده است که عدد $j$ ام، $a_{i,j}$، نمایانگر قیمت کارخانه‌ی $i$ ام برای جنس $j$ ام است. $$ 1 \le n \le 100 $$ $$ 1 \le m \le 16 $$ $$ 1 \le d_i,a_{i,j} \le 1\ 000\ 000 $$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که نمایانگر کمینه‌ی هزینه برای خرید این $m$ جنس است. # مثال ## ورودی نمونه ۱ ``` 2 2 1 1 1 5 5 5 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 3 4 5 7 3 7 9 2 1 20 3 2 8 1 20 1 1 ``` ## خروجی نمونه ۲ ``` 16 ``` توضیح: در نمونه‌ی اول پروفسور به کارخانه‌ی اول رفته و تمام اجناس را خریداری می‌کند و برمی‌گردد.در نمونه‌ی دوم: او ابتدا به کارخانه‌ی دوم رفته و اجناس شماره‌ی یک،سه و چهار را خریداری ‌می‌کند و سپس به فروشگاه رفته، اجناس را تحویل می‌دهد(تا اینجا $8$ واحد هزینه داده‌است.) و بعد برای خرید جنس شماره‌ی دو به کارخانه‌ی اول رفته و آن را خریداری می‌کند و به فروشگاه برمی‌گردد(برای بدست‌آوردن جنس دوم هم $8$ واحد پول هزینه می‌کند که در مجموع می‌شود $16$).

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، به بازی پو روی آورده. او امروز بخش جدیدی از این بازی را پیدا کرده و می‌خواهد آن را به روش خود انجام دهد. این بازی روی صفحه‌ی تبلتش انجام می‌شود. فرض کنید که صفحه‌ی تبلت او مانند یک صفحه مختصات دکارتی است که اضلاع پایین و چپ صفحه‌ی تبلت، محور‌های مختصات $x$ و $y$ هستند. $n$ نقطه روی این صفحه وجود دارند. این نقاط را با اعداد ۱ تا $n$ شماره گذاری میکنیم. نقطه‌ی $i$ام روی مختصات $(x_i, y_i)$ قرار گرفته‌ است. پروفسور باید روی تبلتش، دست خود را روی نقطه‌ی ۱ گذاشته و دست خود را موازی محور های مختصات (بصورت عمودی و افقی) روی صفحه‌ی تبلت حرکت دهد تا دستش به نقطه‌ی $n$ برسد و در طی این حرکت، روی صفحه‌ی تبلت در مسیر دست او خطی شکلاتی کشیده میشود. از قابلیت‌های این بازی، توانایی حرکت بین نقاط است. یعنی پروفسور می‌تواند برای کشیدن مسیری از نقطه‌ی $s$ به نقطه‌ی $t$، ابتدا مسیری بین نقطه‌ی $s$ و نقطه‌ی $i$ روی تبلت بکشد، سپس دست خود را برداشته و پس از استراحت، دوباره دستش را روی تبلت گذاشته و مسیری بین نقطه‌ی $i$ و نقطه‌ی $t$ را روی تبلت بکشد. پروفسور، امروز خیلی ناشیانه بازی کرده است؛ بطوری که دستش درد گرفته و حرکت عمودی دستش روی تبلت (در راستای محور $y$) برایش خیلی سخت است. اما پروفسور هنوز هم می‌خواهد به بازی ادامه دهد، و تلاش میکند طوری بازی کند که دستش کمترین مقدار حرکت عمودی را انجام دهد. برای رسیدن به این هدف او میتواند وقتی دستش روی صفحه‌ی تبلت نیست، تبلت را ۹۰ درجه بچرخاند! برای مثال اگر پروفسور بخواهد از نقطه‌ی ۱ با مختصات $(9, 0) $ به نقطه‌ی $n$ با مختصات $(5, 8)$ مسیری بکشد، بدون چرخاندن تبلت باید دستش ۸ واحد در راستای عمودی حرکت کند ولی اگر تبلت را ۹۰ درجه بچرخاند، می‌تواند با تنها ۴ واحد حرکت در راستای عمودی به هدفش برسد. اگر نقطه‌ی ۲ با مختصات $(5, 0)$ نیز روی صفحه وجود داشته باشد، پروفسور میتواند ابتدا بدون حرکت دادن دستش در راستای عمودی خطی از نقطه‌ی ۱ به نقطه‌ی ۲ بکشد و سپس دست خود را برداشته و تبلت را بچرخاند. حال میتواند باز هم بدون حرکت دست در راستای عمودی، خطی از نقطه‌ی ۲ به نقطه‌ی $n$ بکشد و در مجموع بدون حرکت دادن دستش بصورت عمودی، به هدفش برسد. با ورودی گرفتن مختصات نقاط، به پروفسور بگویید که حداقل مقدار حرکت عمودی دستش برای اینکه مسیری از نقطه‌ی ۱ به نقطه‌ی $n$ روی تبلتش بکشد چقدر است. # ورودی سطر اول ورودی شامل عدد $n$ است که نشان دهنده‌ ی تعداد نقاط روی صفحه است. در سطر $i$ام از هریک از $n$ سطر بعدی مختصات نقطه‌ی $i$ بصورت $x_i\ y_i$ آمده است. $$ 2 \le n \le 200\ 000$$ $$ 0 \le x_i, y_i \le 1000\ 000\ 000$$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که برابر است با کمترین مقدار حرکت عمودی دست که برای کشیدن مسیری بین نقطه‌ی ۱ و نقطه‌ی $n$ لازم است. # مثال ## ورودی نمونه ۱ ``` 2 9 0 5 8 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 3 9 0 5 0 5 8 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 5 2 2 1 1 4 5 7 1 6 7 ``` ## خروجی نمونه ۳ ``` 2 ```

+ محدودیت ز مان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، به دیدن مسابقات شتردوانی پارالمپیک رفته است. شترها و سوارهایشان در هنگام شروع مسابقه، در یک خط و پشت سر هم قرار گرفته‌اند؛ یعنی شتر $i$ ام، در هنگام شروع مسابقه، در جایگاه $i$ ام جدول قرار دارد. با صدای بوق، مسابقه آغاز می‌شود(اگر مسابقه را با صدای شلیک آغاز می‌کردند امکان داشت که شتر ها رم کرده و مسابقه به هم بریزد). به دلیل ناشی بودن پروفسور، او به جای لذت بردن از مسابقه، تمام مدت در حال شمردن تعداد سبقت‌هایی بود که هر شخص می‌گرفت. یعنی او در دفترچه‌اش، برای هر شترسوار، تعداد بار هایی که او از شترسوار دیگری سبقت گرفته است را یادداشت کرده‌است. بعد از مسابقه او به خانه برمی‌گردد. اما چون خودش می‌داند که ناشی است، شک می‌کند که آیا تعداد سبقت‌ها را درست شمرده‌است یا خیر. از این رو بر آن شد که تعداد سبقت ها را برای هر نفر به شما بدهد و از شما بپرسد که اصلا آیا امکان دارد مسابقه‌ای برگزار شود که در آن نفر $i$ ام که در موقع شروع مسابقه در جایگاه $i$ ام بود، $a_i$ بار سبقت بگیرد؟ برای راحتی شما(یا شایدم سختی شما) می‌توانید فرض کنید که سبقت‌ها در زمان‌های مختلف صورت می‌گیرد یعنی هیچ دو شترسواری در یک لحظه همزمان سبقت نمی‌گیرند (بالاخره پروفسور اگر چه ناشیه، ولی خیلی مهربونه). # ورودی در هر ورودی، تعدادی تست آمده‌است که برنامه‌ی شما باید به آن‌ها به ترتیب پاسخ دهد. در سطر اول هر ورودی یک عدد $t$ آمده است که نمایانگر تعداد تست‌هایی است که باید در این ورودی جواب داده شوند. سپس در هر تست: در سطر اول هر تست یک عدد $n$ آمده‌ است که نمایانگر تعداد شترسوار ها در این تست است. در سطر دوم تست، $n$ عدد آمده است که عدد $i$ ام، $a_i$، نمایانگر تعداد سبقت‌هایی است که نفر $i$ ام گرفته‌است. $$ 1 \le n \le 1\ 000\ 000 $$ $$ 0 \le a_i \le 1\ 000\ 000\ 000$$ مجموع $n$ در تست‌های هر ورودی از $ 2\ 000\ 000 $ بیشتر نیست. # خروجی در تنها سطر خروجی هر تست یکی از دو کلمه‌ی زیر را خروجی دهید: + No: به معنای اینکه مسابقه‌ای با این تعداد سبقت برای هر نفر ممکن نیست + Yes: به معنای اینکه مسابقه‌ای با این تعداد سبقت برای هر نفر ممکن است # مثال ## ورودی نمونه ``` 3 2 0 1 3 0 1 4 3 1 1 3 ``` ## خروجی نمونه ``` Yes No Yes ``` توضیح: در تست اول اگر نفر دوم از نفر اول سبقت بگیرد و هیچ سبقت دیگری اتفاق نیفتد، درست می‌شود. در تست سوم: نفرات اول و دوم و سوم را به ترتیب اصفر، اکبر و مهدی می‌نامیم. حالا به ترتیب سبقت‌ها اینگونه می‌شوند: مهدی از اکبر، اکبر از مهدی، مهدی از اکبر، مهدی از اصغر، اصغر از مهدی.