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

باب یک تلویزیون جدید خریده‌است که $n$ شبکه دارد. اسم هر شبکه یک رشته از حروف انگلیسی کوچک است.

کنترل تلویزیون باب یک کلید دارد که شبکه‌ی کنونی را به شبکه‌ی دیگری تغییر می‌دهد (شبکه‌ها به ترتیب از ۱ تا $n$ شماره گذاری شده‌اند). اگر تلویزیون در شبکه‌ی $i$ ام باشد با فشردن کلید آن دو حالت زیر می‌تواند اتفاق بیفتد:

• اگر $i$ کمتر از $n$ باشد به شبکه‌ی $i + 1$ تغییر پیدا می‌کند.
• اگر $i$ برابر $n$ باشد به شبکه‌ی $1$ تغییر پیدا می‌کند.

اگر تلویزیون در ابتدا $x$ امین شبکه را نشان‌دهد، نام شبکه‌ای که پس از آن که باب کلید کنترل تلویزیون را $k$ بار بفشارد تلویزیون نمایش می‌دهد، چه خواهد‌بود؟

ورودی🔗

ابتدا $n$ داده می‌شود که برابر تعداد شبکه‌های تلویزیون است. سپس $x$ داده می‌شود که شماره‌ی شبکه‌ی اوّلیه‌ی تلویزیون است. سپس $k$ که تعداد دفعاتی است که باب کلید کنترل تلویزیون را می‌فشارد.

سپس $n$ رشته که در $i$-امین خط بعد نام شبکه‌ی $i$-ام داده‌ می‌شود. طول نام هر شبکه حداکثر $100$ است و نام هیچ دو شبکه‌ای یکسان نیست.

$1 \le n,k \le 100$ $1 \le x \le n$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

5 2 5
bob
carl
kevin
phil
tim

خروجی نمونه🔗

carl

شبکه ها این گونه تغییر می‌کنند:

 carl > kevin > phil > tim > bob > carl

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

کِوین در حال اتمام کتاب مورد علاقه‌ش برای ۷۴مین بار است که...

کتاب کِوین*، $n$ برگ دارد (جلد‌های ابتدا و انتها جزو برگ‌های کتاب به حساب نمی‌آیند). او از خواندن این کتاب خسته‌شده است و تصمیم می‌گیرد که میانگین صدای *شالاپ تولید شده توسط بستن سریع و با‌قدرت کتاب را بدست آورد. او به صورت کاملاً شانسی و با احتمال برابر، یکی از صفحه‌هایش را باز می‌کند. اگر کتاب را از یک صفحه باز کنیم قدرت شالاپش برابر مقدار کوچک‌تر بین تعداد برگ‌های قرار گرفته روی هر یک از دو جلد است (تعداد آن های می‌تواند ۰ تا $n$ باشد).

با داشتن تعداد برگ‌های کتاب میانگین صدای شالاپ کتاب کِوین را بدست آورید. به عبارت دیگر میانگین صدای شالاپ تولید‌شده برابر است با:

$\frac{\sum_{i=0}^{n} min(i,n-i)}{n+1}$

که $min(a,b)$ برابر مقدار کوچکتر بین $a$ و $b$ است.

ورودی🔗

در تنها خط ورودی عدد $n$ که برابر تعداد برگ‌های کتابِ کِوین است داده می‌شود. $0\le n \le 2 \times 10^9$

خروجی🔗

در تنها خط خروجی میانگین صدای شالاپ کتاب را چاپ کنید. جواب شما در صورتی قبول می‌شود که اختلاف آن با جواب اصلی از $10^{-6}$ بیشتر نشود.

مثال🔗

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

3

توضیح:

1. اگر ۰ برگ روی جلد چپ قرار داشته‌باشد و ۳ برگ رو جلد راست قرار‌ داشته‌باشد صدایش قدرت ۰ را دارد،
2. اگر ۱ برگ روی جلد چپ قرار داشته‌باشد و ۲ برگ رو جلد راست قرار‌ داشته‌باشد صدایش قدرت ۱ را دارد،
3. اگر ۲ برگ روی جلد چپ قرار داشته‌باشد و ۱ برگ رو جلد راست قرار‌ داشته‌باشد صدایش قدرت ۱ را دارد،
4. اگر ۳ برگ روی جلد چپ قرار داشته‌باشد و ۰ برگ رو جلد راست قرار‌ داشته‌باشد صدایش قدرت ۰ را دارد،

پس جواب برابر $\frac{0+1+1+0}{4}$ می‌شود.

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

0.500000

توضیح: جواب را می‌توانید به صورت ‍0.50000 یا به صورت 0.5 یا به صورت 0.50000000 نیز خروجی‌دهید.

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

21

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

5.000000

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

باب جدیداً با موتور جستجوی هوشمند خرید ترب آشنا شده و در حال نوشتن نام کالای مورد نظرش در بخش جستجوی سایت است.

در موتور جستجوی هوشمند خرید ترب $n$ نوع کالا وجود دارد که اسم هر‌ کدام از تعدادی کلمه تشکیل شده است. ترب پیش‌بینی کرده است که احتمال آن که کسی کالای شماره‌ی $i$ را بخرد، برابر $\frac{p_i}{1 \ 000 \ 000}$ است.

موتور جستجوی هوشمند خرید ترب یک سیستم تکمیل خودکار دارد که این‌گونه عمل می‌کند که بین کالاهایی که عبارت وارد شده توسط کاربر پیشوند نام آن کالا است، کالایی که بیشترین احتمال جستجو شدن (یا همان $\frac{p_i}{1 \ 000 \ 000}$ ) را دارد را انتخاب می‌کند ( اگر چند کالا با بیشترین احتمال خرید وجود داشت، کالایی که از نظر ترتیب الفبایی کوچک‌ترین است انتخاب می‌شود). تضمین می‌شود که حتما سیستم تکمیل خودکار می‌تواند کالایی را برای تکمیل شناسایی کند.

نام $a$ ($a_1,a_2,..,a_x$) پیشوند نام $b$ ($b_1,b_2,...,b_y$) است اگر $x \le y$ و $a_1=b_1,a_2=b_2,...,a_x=b_x$ هر‌دو صادق باشد و $a_i$ و $b_i$ها هر‌کدام یک کلمه باشند.

در ترتیب الفبایی کلمه $a$ کوچک‌تر از کلمه $b$ است اگر یکی از دو شرط زیر برقرار باشد:

1. کلمه $a$ پیشوند $b$ باشد.

2. اندیس $i$-ای وجود داشته باشد که $a_1=b_1,a_2=b_2,...,a_{i-1}=b_{i-1}$ و $a_i$ در الفبا قبل از $b_i$ بیاید. الفبا در اینجا همان کد اسکی است.

   برای مثال کلمه abc کوچک‌تر از abcde است و کلمه abcd کوچک‌تر از abgd است.

مقایسه‌ی نام‌ها همانند کلمات است ولی در $a_i$ ها و $b_i$ ها به جای حروف کلمات می‌آیند.

باب در ترب $m$ بار جستجو کرده‌است. با داشتن نام و احتمال‌های جستجو‌ی هر کالا و جستجو‌ی های باب*، نام کالایی که سیستم تکمیل خودکار *ترب برای هر جستجو بدست می‌آورد را خروجی‌دهید.

تضمین می‌شود مجموع تمام احتمال‌ها برابر $1$ می‌شود.

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

ورودی🔗

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

در هر یک از $n$ خط بعد ابتدا عدد $k$ داده‌ می‌شود که تعداد کلمات نام آن کالا است. سپس در همان خط عدد $p_i$ داده می‌شود که احتمال آن است کسی بخواهد آن کالا را بخرد. سپس در همان خط $k$ رشته داده می‌شود که کلمات نام آن کالا است. طول هر یک از کلمات حداکثر $10$ است و از ارقام و حروف انگلیسی تشکیل شده‌اند.

در هر یک از $m$ خط بعد ابتدا عدد $k$ که تعداد کلمات نوشته‌شده توسط باب به ازای هر جستجو است و سپس در همان خط $k$ رشته که کلماتی است که باب به ازای آن جستجو نوشته‌است داده می‌شود. $1\le n,m \le 1\ 000$ $0\le p_i \le 1\ 000\ 000$ $1\le k\le 5$ $\sum_{i=1}^{n} p_i = 1 \ 000 \ 000$

خروجی🔗

در هر یک از $m$ خط خروجی به ازای هر یک از جستجو‌های باب نام کالایی که سیستم تکمیل خودکار موتور جستجوی هوشمند ترب تشخیص می‌دهد را خروجی دهید.

مثال🔗

ورودی نمونه🔗

4 5
4 100000 Smartphone Samsung Galaxy s8
3 200000 Smartphone iPhone 8
4 300000 Smartphone Samsung Galaxy s8plus
4 400000 Smartphone iPhone X gray256gb
1 Smartphone
3 Smartphone iPhone X
4 Smartphone iPhone X gray256gb
2 Smartphone iPhone
4 Smartphone Samsung Galaxy s8plus

خروجی نمونه🔗

Smartphone iPhone X gray256gb 
Smartphone iPhone X gray256gb 
Smartphone iPhone X gray256gb 
Smartphone iPhone X gray256gb 
Smartphone Samsung Galaxy s8plus

توضیح: برای جستجوی اول کالا‌های نوع های ۱و۲و۳و۴ ممکن است مورد خواست باب باشد و در بین آن ها کالای نوع ۴ از همه احتمال بیشتری را دارد. برای دومین جستجو فقط کالای نوع ۴ امکان‌پذیر است. برای سومین جستجو نیز فقط کالای نوع ۴ امکان‌پذیر است. برای چهارمین جستجو کالاها‌ی نوع ۲و۴ امکان‌پذیر هستند و در بین آن‌ها کالای‌ شماره‌ی ۴ احتمال بیشتری دارد. برای پنجمین جستجو فقط کالای نوع ۳ امکان‌پذیر است.

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

کِوین از کودکی علاقه‌ی زیادی به اعداد باینری (صفر و یکی) داشته‌است، این داستان یکی از کار‌هایی است که او با آن‌ها می‌کرده‌است.

اگر رشته باینری را به صورت $s_1,s_2,...,s_n$ نشان‌دهیم و $n$ برابر طول آن باشد، زیبایی رشته برابر تعداد ۴ تایی‌های $s_i,s_j,s_k,s_l$ که هر کدام یک بیت (یا صفر یا یک است) از رشته‌اند که $1\le i<j<k<l \le n$ و $s_i \ and \ s_j \; = \; s_j \ or \ s_k \; = \; s_k \ nand \ s_l \; = \; s_l \ xor \ s_i$ است.

کوِین به شما رشته‌ی باینری $s$ را داده‌است، زیبایی آن را بدست آورید.

به دلیل این که زیبایی رشته‌ی $s$ می‌تواند زیاد باشد. باقی‌مانده‌ی تقسیم زیبایی آن را بر $10^9+7$ چاپ کنید.

برای آشنایی با عملگر‌های بیتی اینجا را بخوانید.

ورودی🔗

در تنها خط ورودی رشته‌ی $s$ داده می‌شود. دقت کنید که $s$ می‌تواند با صفر شروع شود. $4 \le |s| \le 500 \ 000$

منظور از $|s|$ طول رشته‌ی $s$ است.

خروجی🔗

در تنها خط خروجی باقی‌مانده‌ی تقسیم زیبایی رشته‌ی $s$ را بر $10^9+7$ را چاپ کنید.

مثال🔗

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

1010101

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

2

توضیح: چهار‌تایی‌ها‌ی $s_1,s_3,s_4, s_6$ و چهار تایی $s_1,s_3,s_5,s_6$ معتبر اند.

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

01100100

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

10

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

باب توانایی هوشی بالایی ندارد، اما عجیب این است که به دنباله‌های k-حسابی علاقه‌ی زیادی دارد.

یک دنباله k-حسابی یک دنباله غیر‌نزولی از اعداد صحیح است که اختلاف هر دو عضو مجاورش دقیقا $k$ است.

کِوین به باب دنباله‌ی $a_{1},a_{2},...,a_{n}$ را داده‌است، باب می‌خواهد این دنباله را به یک دنباله‌ی k-حسابی تبدیل کند. باب در هر مرحله می‌تواند یک عضو دلخواه را یک واحد کاهش یا افزایش دهد. او می‌خواهد بداند که حداقل چند مرحله نیاز است که دنباله به یک دنباله k-حسابی تبدیل شود.

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. سپس در سطر بعد $n$ عدد صحیح $a_{1},a_{2},...,a_{n}$ آمده است. $1\le n \le 500 \ 000$ $0\le k \le 100$ $|a_{i}| \le 10^9$

خروجی🔗

در تنها سطر خروجی حداقل تعداد مرحله‌ای که باب نیاز دارد انجام دهد که دنباله‌اش k-حسابی شود را چاپ کنید.

مثال🔗

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

3 1
1 3 5

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

2

توضیح: اگر دنباله را به $2,3,4$ تبدیل کنیم جواب حداقل می‌شود.

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

4 3
1 2 3 4

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

8

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

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

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

حداکثر مساحت بین زیرمجموعه‌های ماکسیمال هم‌بند از خانه‌‌های سفید که تمامی خانه‌های آن در بین خانه‌های قرمز محصور باشد، برابر امنیت حرکات ما است. حال کِوین به شما یک روش حرکت در جدول را داده‌است و از شما می‌خواهد که امنیت حرکات را بدست آورید.

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

برای درک بهتر سوال به مثال‌ها توجه کنید.

ورودی🔗

در تنها خط ورودی رشته‌ی $s$ داده‌می‌شود که هر خانه از آن:

• اگر R باشد یعنی حرکت به سمت راست است.
• اگر L باشد یعنی حرکت به سمت چپ است.
• اگر D باشد یعنی حرکت به سمت پایین است.
• اگر U باشد یعنی حرکت به سمت بالا است.

$1 \le |s| \le 400 \ 000$

منظور از $|s|$ طول رشته‌ی $s$ است.

خروجی🔗

در تنها خط خروجی امنیت حرکات را خروجی دهید.

مثال🔗

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

RDRURDRDLU

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

0

توضیح: حرکات به این شکل می‌شود: (. همان خانه‌های سفید است و ‍R خانه‌های قرمز است و ‍S نقطه‌ی شروع است)

..........
..........
..........
..........
....SRRR..
.....RRRR.
.......RR.
..........
..........
..........

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

RRRRDDLLUDLLUUUURRRD

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

2

توضیح: حرکات به این شکل می‌شود: (. همان خانه‌های سفید است و ‍R خانه‌های قرمز است و ‍S نقطه‌ی شروع است)

..........
..RRRR....
..R..R....
..SRRRR...
..R.R.R...
..RRRRR...
..........
..........
..........
..........

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

RDDLLU

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

1

توضیح: حرکات به این شکل می‌شود: (. همان خانه‌های سفید است و ‍R خانه‌های قرمز است و ‍S نقطه‌ی شروع است)

........
........
...SR...
..R.R...
..RRR...
........
........

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

RRRRUUUULLLLDDDDDDDLLLUUURRR

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

9

توضیح: حرکات به این شکل می‌شود: (. همان خانه‌های سفید است و ‍R خانه‌های قرمز است و ‍S نقطه‌ی شروع است)

............
............
.....RRRRR..
.....R...R..
.....R...R..
.....R...R..
..RRRSRRRR..
..R..R......
..R..R......
..RRRR......
............
............

این شکل تنها دو زیرمجموعه هم‌بند ماکسیمال دارد که اندازه یکی ۹ و دیگری ۴ است. پس امنیت آن برابر ۹ می‌شود.

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

صورت این سوال نسبتا‌ً طولانی بود و نمی‌توانستیم شخصیت خاصی را داخلش جا بدهیم، اما نوبت باب است و اگر در سوال نباشد ناراحت می‌شود پس مجبور شدیم یک جایی در این سوال اسمش را بیاوریم.

قدرت دنباله‌ی اعداد $a_1,a_2,...,a_n$ برابر مجموع زیبایی تمام افراز های آن به تعدادی بخش (نه لزومن متوالی) است.

زیبایی افراز یک دنباله به تعدادی بخش برابر: $\sum_{i=1}^k s_{i} \times p_{c_{i}}$ است که در آن $s_i$ برابر مجموع اعداد بخش $i$-ام از افراز است و $c_i$ برابر تعداد اعضای بخش $i$-ام از افراز است و $k$ تعداد بخش‌های افراز است و $p_1,p_2,...,p_n$ دنباله دیگری است که به صورت جداگانه در ورودی داده می‌شود. دقت کنید که اعداد برچسب‌دار هستند، یعنی دو عدد برابر در دنباله متفاوت هستند. برای مثال در دنباله‌ی $[1,2,2]$ افراز $[[1,2],[2]]$ دو بار شمارده‌ می‌شود، یک بار برای اوّلین $2$ یک بار هم برای دوّمین $2$ شمارده‌ می‌شود.

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

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

باب به شما دنباله‌ی $a_1,a_2,...,a_n$ و دنباله‌ی $p_1,p_2,...,p_n$ را داده‌ است و سپس $q$ درخواست به شما می‌دهد، که هر درخواست به یکی از اشکال زیر است :

1. به شما سه عدد $l \ r \ x$ داده‌ می‌شود و از شما می‌خواهد که تمام اعداد $a_{l},...,a_r$ را $x$ واحد افزایش دهید.
2. به شما دو عدد $l \ r$ داده ‌می‌شود و از شما می‌خواهد که قدرت‌محض دنباله‌ی $a_{l},...,a_r$ را خروجی‌دهید.

به دلیل این که قدرت‌محض دنباله می‌تواند بزرگ باشد، باقی‌مانده‌اش را در تقسیم آن بر $10^9+7$ را خروجی دهید. دقت کنید که فقط در انتها با‌قی‌مانده گرفته می‌شود و در تمام مراحل بدست آوردن قدرت‌محض، خود اعداد در نظر گرفته‌ می‌شوند و بزرگی باقی‌مانده آن‌ها در تقسیم بر $10^9+7$ مد نظر نیست.

ورودی🔗

در خط اول ابتدا $n$ که تعداد اعضای دنباله‌ی $a$ و $p$ است و سپس $q$ که تعداد در‌خواست‌ها است داده‌ ‌می‌شود. سپس در خط بعدی $n$ عدد به‌ شما داده می‌شود که عدد $i$-ام همان $a_i$ است. سپس در خط بعدی $n$ عدد به‌ شما داده می‌شود که عدد $i$-ام همان $p_i$ است. سپس در $q$ خط بعدی به شما در‌خواست‌ها داده‌ می‌شود که به‌ صورت زیر داده‌ می‌شود:

1. به صورت $1 \ l \ r \ x$ داده‌ ‌می‌شود که همان درخواست نوع اول است.
2. به صورت $2 \ l \ r$ داده ‌می‌شود که همان در‌خواست نوع دوم است.

$1 \le n \le 5 \ 000$ $1 \le q \le 500 \ 000$ $0 \le a_i,p_i,x \le 10^9$ $1\le l \le r \le n$

خروجی🔗

در خروجی به ازای هر درخواست نوع دوم باقی‌مانده قدرت‌محض آن بخش خواسته‌شده بر $10^9+7$ را چاپ کنید.

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

3 3
1 2 3
6 3 2
2 1 3
1 1 3 1
2 1 3

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

120
180

توضیح برای درخواست اوّل: اگر دنباله را به $[3,0,3]$ تبدیل کنیم، قدرت آن ماکسیمم می‌شود:

• قدرت $[[3,0,3]]$ برابر $12$ است.
• قدرت $[[3,0],[3]]$ برابر $27$ است.
• قدرت $[[0,3],[3]]$ برابر $27$ است.
• قدرت $[[3,3],[0]]$ برابر $18$ است.
• قدرت $[[3],[0],[3]]$ برابر $36$ است.

که قدرت‌محض آن می‌شود : $12+27+27+18+36=120$

توضیح برای درخواست دوّم: اعضای اوّل تا سوّم دنباله یک واحد افزایش پیدا میکنند و دنباله‌ی $[1, 2, 3]$ به دنباله‌ی $[2, 3, 4]$ تغییر پیدا می‌کند.

توضیح برای درخواست سوّم: اگر دنباله را به $[4,0,5]$ تبدیل کنیم، قدرت آن ماکسیمم می‌شود:

• قدرت $[[4,0,5]]$ برابر $18$ است.
• قدرت $[[5,0],[4]]$ برابر $39$ است.
• قدرت $[[4,0],[5]]$ برابر $42$ است.
• قدرت $[[4,5],[0]]$ برابر $27$ است.
• قدرت $[[5],[0],[4]]$ برابر $54$ است.

که قدرت‌محض آن می‌شود : $18+39+42+27+54=180$

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

3 3
1 2 3
6 3 3
1 1 2 2
1 1 3 3
2 1 3

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

399

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

کِوین جدیدا با کار دریا‌نوردی آشنا شده‌است. او در حال سفر در دریایی بزرگ است که مسئله‌ای به ذهنش می‌رسد...

دریایی که کِوین در آن قرار دارد جدولی از چهار طرف نامتناهی است، ولی ما تنها در مورد یک زیرجدول $n$ در $m$ از آن اطلاع داریم و می‌دانیم که بجز خشکی‌های داخل این زیر‌جدول، ‌در این دریا خشکی دیگری وجود ندارد.

برای درک بهتر مسأله‌ی او ابتدا تعاریف مورد نیاز مساله‌اش را بیان می‌کنیم:

• خانه‌های مجاور هر خانه تمام خانه‌هایی اند که حداقل یک را‌ٔس مشترک با‌ آن دارند. هر خانه در جدول ۸ خانه مجاور دارد.
• جزیره به مجموعه‌ای ماکسیمال (یعنی هیچ خانه‌ی خشکی‌ای وجود ندارد که مجاور حداقل یکی از خانه‌های آن باشد و عضوی‌ از مجموعه نباشد) از خانه‌های خشکی است که همبند (بین هر دو خانه‌ای از آن مسیری شامل خانه‌های خشکی وجود دارد) است.
• یک مسیر دریایی به دنباله‌ای از خانه‌های آبِ مجاور گفته‌ می‌شود که دو خانه‌ی خشکی را به هم وصل می‌کنند.
• اگر بین دو جزیره یک مسیر دریایی وجود داشته باشد آن دو جزیره دوست دریایی یکدیگر نامیده می‌شوند.
• به دنباله‌ای از تعدادی جزیره دو به دو متمایز که هر دو جزیره متوالی از آن دوست دریایی یکدیگر باشند مسافرت گفته می‌شود.

کِوین می‌خواهد از هر کدام از جزیره‌های این دریا دقیقا یک‌بار دیدن بکند و تمام کالاهای موجود را جمع‌آوری کند. او می‌خواهد که این کار در کمترین تعداد مسافرت ممکن انجام شود. به او کمک کنید که این مسئله‌ را حل کند.

ورودی🔗

ورودی شامل یک خط است که در آن دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است. $1 \le n,m \le 1 \ 000$ سپس یک جدول $n$ در $m$ که از . یا # تشکیل شده است داده می‌شود. . نشان دهنده آب و # نشان دهنده خشکی است.

خروجی🔗

در تنها خط خروجی تعداد مسافرتهای لازم را خروجی‌‌دهید.

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

5 5
#.#.#
..#..
#####
..#..
#.#.#

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

1

توضیح: $*$ مسیر مسافرت را نشان می‌دهند:

.........
..***....
..#.#*#*.
....#..*.
..#####*.
....#..*.
..#.#*#*.
..****...
.........

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

7 17
###############.#
#.#####.#####.#..
#.#...#.#...#.#..
#.#.#.#.#.#.#.#..
#.#...#.#...#.#..
#.#####.#####.#..
###############..

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

2

توضیح: $*$ مسیر مسافرت را نشان می‌دهند:

.....................
.....................
..###############*#*.
..#.#####.#####.#....
..#.#.*.#.#...#.#....
..#.#.#.#.#.#*#.#....
..#.#...#.#...#.#....
..#.#####.#####.#....
..###############....
.....................
.....................