+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- محمد مهدی تصمیم گرفته تا بازی کند! او در این بازی یک عدد تصادفی از ۱ تا ۱۰۰۰ مثل $n$ انتخاب کرده و $q$ تا از مقسوم علیه‌های آنرا به روزبه می‌گوید. حال روزبه تصمیم گرفته تا عدد محمد مهدی را حدس بزند. روزبه برای اینکه عدد را حدس بزند می‌خواهد بداند که چند عدد وجود دارند که می‌توانند حدس محمد مهدی باشند. به او کمک کنید. # ورودی خط اول ورودی عدد $q$ آمده است. $(1 \leq q \leq 100)$ در خط دوم $q$ عدد که با فاصله از هم جدا شده‌اند که برخی از مقسوم علیه‌های $n$ هستند، آمده است. # خروجی در خروجی تعداد اعدادی که می توانند حدس محمدمهدی باشند را چاپ کنید. دقت کنید ممکن است محمدمهدی اشتباه کرده‌باشد و حدسی وجود نداشته‌باشد. # مثال ## ورودی نمونه ۱ ``` 4 2 3 5 7 ``` ## خروجی نمونه ۱ ``` 4 ``` ---------- ## ورودی نمونه ۲ ``` 1 1 ``` ## خروجی نمونه ۲ ``` 1000 ``` # توضیحات در مثال اول، محمد مهدی یکی از اعداد ۲۱۰، ۴۲۰، ۶۳۰ یا ۸۴۰ را انتخاب کرده‌است. در مثال دوم، محمد مهدی می‌تواند همه‌ی اعداد ۱ تا ۱۰۰۰ را انتخاب کرده‌باشد!

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- محمدمهدی و روزبه برای گشت‌و‌گذار به صفرقند رفته اند. صفرقند شهری عجیب و مالیاتی عجیب دارد! در حین گشت و گذار ناگهان محمدمهدی روزبه را گم می‌کند! او می‌داند که صفرقند یک صفحه‌ی مختصات دکارتی است و او در در مختصات $(x_m, y_m)$ قرار دارد. همچنین متوجه می‌شود که روزبه در مختصات $(x_r, y_r)$ است. اما دیدار دوباره‌ی روزبه به این سادگی نیست! :( صفرقند دارای تعدادی ناحیه است، هر ناحیه یک مستطیل که اضلاع آن با محور $x$ها و $y$ها موازی است. عبور از مرز‌ هر ناحیه یک تومان مالیات دارد. همچنین می‌دانیم به ازای هر دو ناحیه از صفرقند، این دو ناحیه یا اشتراکی ندارند یا یکی زیرناحیه‌ی دیگری ‌است. حال محمد مهدی می‌خواهد بداند حداقل باید چقدر مالیات بدهد تا به روزبه برسد. به او کمک کنید... # ورودی در سطر اول ورودی $x_m, y_m$ که مختصات محمدمهدی است آمده است. $(-10^9 \leq x_m, y_m \leq 10^9)$ در سطر دوم ورودی $x_r, y_r$ که مختصات روزبه است آمده است. $(-10^9 \leq x_r, y_r \leq 10^9)$ در سطر سوم ورودی عدد $n$ تعداد ناحیه‌های صفرقند آمده‌است. $(0 \leq n \leq 3\times10^4)$ در $n$ سطر بعد، در سطر $i$ام، ۴ عدد $x_1, y_1, x_2, y_2$ که مختصات نقطه‌ی پایین-چپ و بالا‌-راست ناحیه‌است. $(-10^9 \leq x_1 < x_2 \leq 10^9 , -10^9 \leq y_1 < y_2 \leq 10^9)$ تضمین می‌شود که محمد مهدی و روزبه روی مرز‌های ناحیه‌ها نیستند. دقت کنید قرار گرفتن روی مرز نواحی هزینه‌ای ندارد بلکه تنها عبور از ناحیه برای ورود/خروج به آن ناحیه مالیات دارد. # خروجی در تنها سطر خروجی میزان پولی که باید محمدمهدی خرج کند را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 0 0 2 2 1 -1 -1 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ---------- ## ورودی نمونه ۲ ``` 1 1 7 1 6 0 0 2 2 0 0 3 3 0 0 5 5 0 0 6 6 -10 -10 10 10 100 100 200 200 ``` ## خروجی نمونه ۲ ``` 4 ``` # توضیحات اگر یک مرز، مرز مشترک $m$ ناحیه باشد. عبور از آن $m$ تومان مالیت دارد. در مثال اول، محمد مهدی در تنها ناحیه‌ی صفرقند قرار دارد و برای دیدن روزبه مجبور است از ناحیه خارج شود پس باید لاآقل ۱ تومان خرج کند. در مثال دوم، محمد مهدی باید از مرز ۴ ناحیه‌ی نخست صفرقند عبور کند تا به روزبه برسد، پس باید لاآقل ۴ تومان خرج کند.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روزبه دنباله‌ای مثل $a_1, a_2, a_3, ..., a_n$ انتخاب کرد و به ازای هر $i$ طول بلندترین زیردنباله‌ی صعودی که به عضو $i$ ام ختم می‌شود را محاسبه کرد و دنباله‌ی $d_1, d_2, d_3, ..., d_n$ را ساخت که $d_i$ بلندترین زیردنباله‌ی صعودی مختوم به $i$ است. روزبه دنباله‌ی $d_1, d_2, ..., d_n$ را به محمدمهدی می‌دهد و از او میپرسد به ازای تمام دنباله‌های ممکن که دنباله‌ی ساخته شده از آن دنباله‌ی $d_1, d_2, ..., d_n$ شود، کمترین طول برای بزرگترین زیردنباله‌ی نزولی آن‌ها چقدر است؟ به محمد مهدی کمک کنید تا پاسخ این پرسش را بدهد. # ورودی خط اول ورودی عدد $n$ که طول دنباله‌است آمده‌است. $(1 \leq n \leq 5\times10^5)$ در خط دوم $n$ عدد که با فاصله از هم جدا شده‌اند آمده‌است که عدد $i$ام مقدار $d_i$ است. # خروجی در خط اول خروجی یک عدد که کمینه طول برای بزرگترین زیردنباله‌ی نزولی برای همه‌ی دنباله‌های ممکن برای انتخاب روزبه است. خط دوم، دنباله‌ای مثال بزنید که طول بلندترین زیردنباله‌ی نزولی آن عدد کمینه باشد. اعضای دنباله‌ی خروجی باید عدد طبیعی بوده و از یک‌میلیون بیشتر نباشند. # مثال ## ورودی نمونه ۱ ``` 5 1 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 1 1 2 3 4 5 ``` ---------- ## ورودی نمونه ۲ ``` 13 1 2 2 3 3 3 3 3 4 5 5 6 7 ``` ## خروجی نمونه ۲ ``` 5 19 74 66 1001 1000 444 323 98 5000 6000 5555 8500 9500 ``` # توضیحات بلندترین زیردنباله‌ی صعودی، زیردنباله‌ای است که با حذف برخی از عضو‌های دنباله‌ی اصلی به دست می‌آید و همچنین صعودی است. بلندترین زیردنباله‌ی نزولی، زیردنباله‌ای است که با حذف برخی از عضوهای دنباله‌ی اصلی به دست می‌آید و همچنین نزولی است. دنباله‌ای مثل $a_1, a_2, ..., a_n$ صعودی‌است اگر و تنها اگر به ازای هر $i$ که $1 \leq i < n$، $a_i \leq a_{i+1}$. دنباله‌ای مثل $a_1, a_2, ..., a_n$ نزولی‌است اگر و تنها اگر به ازای هر $i$ که $1 \leq i < n$، $a_i \geq a_{i+1}$.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدمهدی دارای تعدادی حیوان اسکل است! اسکلان حیواناتی عجیب‌اند و در روزی از سال شروع به کشتن بچه‌های خود می‌کنند. هر اسکل تعداد فرزند دارد. در روز قتل‌عام، اسکل اعظم، بزرگ اسکلان که خود زاده شده از اسکل دیگری نیست، قتل‌عام را شروع می‌کند. او یکی از بچه‌هایش را به احتمال برابر انتخاب کرده و سر آن را از بدن جدا کرده و به محمدمهدی تقدیم می‌کند. دیگر بچه‌های اسکل قربانی کننده و همه‌ی بچه‌های قربانی‌شونده که از این قربانی‌شدن مصون مانده‌اند، برای شکرگزاری، این عمل را تکرار می‌کنند! یعنی یکی از بچه‌هایشان را انتخاب‌کرده و به احتمال برابر قربانی می‌کنند و ... حال محمد مهدی تصمیم‌گرفته تا برای روزبه آشی با سر این اسکلان درست کند. اگر در آش $w$ کیلو سر اسکل باشد، روزبه $w$ کیلو چاق می‌شود. روزبه چند کیلو چاق می‌شود؟ # ورودی در خط اول ورودی عدد $n$ که تعداد اسکل‌هاست آمده است. در خط دوم $n$ عدد که با فاصله از هم جدا‌شده‌اند آمده است که عدد $i$ام برابر با $w_i$ یعنی وزن سر اسکل شماره $i$ است. در خط سوم $n-1$ عدد آمده است که عدد $i$ ام برابر با $a_i$ یعنی پدر اسکل با شماره $i+1$ است. شماره‌ی اسکل اعظم را ۱ در نظر بگیرید. $$ 1 \leq n \leq 10^5 $$ $$ 1 \leq w_i \leq 10^9 $$ # خروجی خروجی شامل یک عدد است که مقداری که روزبه به طور میانگین چاق می‌شود است. دقت کنید اگر پاسخ کد شما $a$ و پاسخ کد اصلی $b$ باشد، کد شما تنها درصورتی مورد قبول قرار می‌گیرد که $\frac{|a-b|}{\max(b, 1)} \leq 10^{-6}$ باشد. # مثال ## ورودی نمونه ۱ ``` 4 1 2 3 4 1 1 2 ``` ## خروجی نمونه ۱ ``` 4.5 ``` # توضیحات در مثال ۱، ورودی به شکل زیر است:  که اسکل اعظم در یک حالت فرزند شماره ۲ را می‌کشد که در این صورت اسکل دیگری نمی‌میرد و در حالت دیگر اسکل شماره ۳ را می‌کشد که در این صورت اسکل شماره ۲ برا شکر‌گزاری، اسکل شماره ۴ را نیز می‌کشد پس به طور میانگین روزبه $ \frac{2 + (3 + 4)}{2} = 4.5$ کیلو چاق می‌شود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- امروز تولد روزبه است و محمدمهدی برای کادوی تولد او یک جدول $n \times n$ خریده است. در هر خانه از این جدول عددی نوشته شده است و همچنین هر خانه از این جدول رنگی دارد! محمد مهدی برای اینکه جدول زیبا شود، تصمیم گرفته تا رنگ برخی از خانه‌های آن را پاک کند. او می‌داند از نظر روزبه جدولی زیباست که در هیچ سطر و ستونی هیچ رنگی دوبار نیاید. اما پاک کردن رنگ به این سادگی نیست! محمد مهدی می‌داند اگر از یک سطر یا ستون، دو خانه را پاک کند، جدول زشت می‌شود! همچنین دیگر دوستان روزبه و محمد‌مهدی، به اندازه‌ی بزرگترین عدد نوشته شده روی خانه‌های پاک شده از او ناراحت می‌شوند :| حال محمدمهدی از این شرایط بسیار گیج شده و کار را به شما می‌سپارد! شما باید ابتدا تعیین کنید آیا محمدمهدی می‌تواند جدول را زیبا کند؟ سپس حداقل میزان ناراحتی دوستانش از او را تعیین کنید. # ورودی سطر اول ورودی عدد طبیعی $n$ آمده است که طول و عرض جدول است. در $i$مین سطر از هریک از $n$ سطر بعدی $n$ عدد طبیعی مانند $c_{i,j}$ آمده است که رنگ خانه در سطر $i$ ام و ستون $j$ ام را مشخص می‌کند. سپس دوباره $n$ سطر می‌آید که سطر $i$ ام شامل $n$ عدد طبیعی مانند $a_{i,j}$ آمده است که عدد نوشته شده در خانه در سطر $i$ ام و ستون $j$ ام را مشخص می‌کند. $$ 1 \leq n \leq 10^3 $$ $$ 1 \leq a_{i, j}, c_{i, j} \leq 10^9 $$ # خروجی اگر محمد مهدی می‌تواند جدول را زیبا کند `Yes` و در غیر اینصورت `No` چاپ کنید. اگر پاسخ `Yes` بود، در سطر دوم حداقل میزان ناراحتی دوستان محمدمهدی از او را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 4 3 1 2 3 6 2 5 1 9 1 3 5 7 9 1 9 ``` ## خروجی نمونه ۱ ``` Yes 3 ``` -------- ## ورودی نمونه ۲ ``` 3 1 2 3 1 2 3 1 2 3 1 9 1 3 5 7 9 1 9 ``` ## خروجی نمونه ۲ ``` No ```