+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پادشاه شهر شکرستان در یک شب پر ستاره از پنجره به بیرون نگاه می‌کند و از تماشای آسمان لذت می‌برد. این پر ستاره بودن آسمان پادشاه را به وجد می‌آورد که ستاره ها را بشمارد. همان‌طور که می‌دانید او همیشه می‌گوید که برای این کار خیلی تنبل است ولی در واقع نمی‌تواند فرق ستاره با سیاره را تشخیص دهد! بنابراین از شما می‌خواهد که کار شمردن ستاره‌ها را برای او انجام دهید. ![توضیح تصویر](http://uupload.ir/files/xu0x_problem1.jpg) تصویر آسمان که از پنجره دیده می‌شود به صورت یک جدول $n \times m$ با $n$ سطر و $m$ ستون است. در هر خانه $ 1 \times 1 $ از این جدول، یک ستاره، یک سیاره و یا خود آسمان دیده می‌شود. و می‌دانیم که هر ستاره و سیاره تنها یک خانه از جدول را اشغال کرده است. در این تصویر یک ستاره به صورت $ "*" $ ، یک سیاره به صورت $ "o" $ و خود آسمان به صورت $ "." $ دیده می‌شود. تعداد ستاره هایی که از پنجره دیده می‌شود را به پادشاه گزارش دهید. # ورودی در یک سطر دو عدد صحیح $n$ و $m$ داده می‌شود. و در $n$ سطر بعدی هر کدام $m$ کاراکتر بدون فاصله داده می‌شود. که این کاراکتر ها $ "*" $ یا $ "o" $ و یا $ "." $ هستند.$$1 \leq n, m \leq 100$$ # خروجی در یک سطر تعداد ستاره ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 4 *.** *.oo o*.o ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 5 1 . o . o * ``` ## خروجی نمونه ۲ ``` 1 ``` ## توضیح نمونه ها: همان طور که در جدول نمونه یک می بینید، ۵ کاراکتر $*$ دیده می شود که هر کدام نشان دهنده ی یک ستاره در آسمان است. و در نمونه ۲ نیز تنها ۱ کاراکتر $*$ دیده می شود.

آسمان شکر آباد

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

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

توضیح تصویر

تصویر آسمان که از پنجره دیده می‌شود به صورت یک جدول $n \times m$ با $n$ سطر و $m$ ستون است. در هر خانه $1 \times 1$ از این جدول، یک ستاره، یک سیاره و یا خود آسمان دیده می‌شود. و می‌دانیم که هر ستاره و سیاره تنها یک خانه از جدول را اشغال کرده است. در این تصویر یک ستاره به صورت $"*"$ ، یک سیاره به صورت $"o"$ و خود آسمان به صورت $"."$ دیده می‌شود. تعداد ستاره هایی که از پنجره دیده می‌شود را به پادشاه گزارش دهید.

ورودی🔗

در یک سطر دو عدد صحیح $n$ و $m$ داده می‌شود. و در $n$ سطر بعدی هر کدام $m$ کاراکتر بدون فاصله داده می‌شود. که این کاراکتر ها $"*"$ یا $"o"$ و یا $"."$ هستند. $1 \leq n, m \leq 100$

خروجی🔗

در یک سطر تعداد ستاره ها را چاپ کنید.

مثال🔗

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

3 4
*.**
*.oo
o*.o

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

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

5 1
.
o
.
o
*

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

توضیح نمونه ها:🔗

همان طور که در جدول نمونه یک می بینید، ۵ کاراکتر $*$ دیده می شود که هر کدام نشان دهنده ی یک ستاره در آسمان است. و در نمونه ۲ نیز تنها ۱ کاراکتر $*$ دیده می شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- گزارشگری از شکرستان برای گرفتن گزارش از $n$ وزیر که در مراسم جشن تولد پادشاه حضور دارند، انتخاب شده است. او روز قبل از مراسم جشن، ساعت برنامه‌ها و حضور وزیران دربار را بررسی می‌کرد. اولین چیزی که فهمید این بود که پادشاه تنها در لحظات ۱ تا $m$ از جشن پیش وزیران می‌آید و هر یک از وزیران تنها در یک بازه‌ی زمانی مانند $[l, r]$ پادشاه را ملاقات می‌کند که ابتدا و انتهای این زمان یک عدد طبیعی است. وقتی بیشتر دقت کرد متوجه شد برای هر دو وزیر لحظه‌ای وجود دارد که هر دوی آنها باهم با پادشاه ملاقات دارند. ![توضیح تصویر](http://uupload.ir/files/d0ch_problem2.jpg) شب قبل از مراسم و ملاقات وزیران با پادشاه، گزارشگر متوجه می شود که بازه‌ی ملاقات یکی از وزیر ها را گم کرده است. حال می‌خواهد بداند که این بازه‌ی زمانی گم شده چند حالت مختلف می‌تواند داشته باشد. # ورودی در خط اول ورودی دو عدد صحیح $n$ و $m$ داده می‌شود که نشان‌دهنده‌ی تعداد وزیران و آخرین زمان دیدار با پادشاه است. در n - 1$ $ خط بعدی در هر خط دو عدد طبیعی $l$ و $r$ داده می‌شود که نشان‌دهنده‌ی بازه‌ی زمانی ملاقات یک وزیر است. تضمین می‌شود که حتماً بازه‌های داده شده شرایط مساله را دارد. $$2 \leq n \leq 200 \ 000$$ $$1 \leq m \leq 200 \ 000$$$$1 \leq l \leq r \leq m$$ # خروجی در تنها خط خروجی یک عدد صحیح که تعداد حالت‌های مختلف برای بازه‌ی زمانی گم شده است را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 4 3 4 ``` ## خروجی نمونه ۱ ``` 7 ``` ## توضیح نمونه ۱: تمام بازه هایی که ممکن است بازه ی گمشده باشد: [4, 4] , [4, 3] , [3, 3], [4, 2], [3, 2] , [4, 1] , [3, 1] ## ورودی نمونه ۲ ``` 2 2 1 1 ``` ## خروجی نمونه ۲ ``` 2 ```

مصاحبه با وزیران

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

گزارشگری از شکرستان برای گرفتن گزارش از $n$ وزیر که در مراسم جشن تولد پادشاه حضور دارند، انتخاب شده است. او روز قبل از مراسم جشن، ساعت برنامه‌ها و حضور وزیران دربار را بررسی می‌کرد. اولین چیزی که فهمید این بود که پادشاه تنها در لحظات ۱ تا $m$ از جشن پیش وزیران می‌آید و هر یک از وزیران تنها در یک بازه‌ی زمانی مانند $[l, r]$ پادشاه را ملاقات می‌کند که ابتدا و انتهای این زمان یک عدد طبیعی است. وقتی بیشتر دقت کرد متوجه شد برای هر دو وزیر لحظه‌ای وجود دارد که هر دوی آنها باهم با پادشاه ملاقات دارند.

توضیح تصویر

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

ورودی🔗

در خط اول ورودی دو عدد صحیح $n$ و $m$ داده می‌شود که نشان‌دهنده‌ی تعداد وزیران و آخرین زمان دیدار با پادشاه است. در n - 1 خط بعدی در هر خط دو عدد طبیعی $l$ و $r$ داده می‌شود که نشان‌دهنده‌ی بازه‌ی زمانی ملاقات یک وزیر است. تضمین می‌شود که حتماً بازه‌های داده شده شرایط مساله را دارد. $2 \leq n \leq 200 \ 000$ $1 \leq m \leq 200 \ 000$ $1 \leq l \leq r \leq m$

خروجی🔗

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

مثال🔗

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

2 4
3 4

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

توضیح نمونه ۱:🔗

تمام بازه هایی که ممکن است بازه ی گمشده باشد: [4, 4] , [4, 3] , [3, 3], [4, 2], [3, 2] , [4, 1] , [3, 1]

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

2 2
1 1

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- وزیر شهر شکرستان می‌خواهد از $n$ نفر از اشراف، زمین کشاورزی بخرد و آن را به مردم بفروشد. همه‌ی زمین ها به شکل یک مربع $1 \times 1$ و کنار هم، در یک ردیف قرار دارند. هر یک از این اشراف برای زمین خودش یک قیمت به وزیر اعلام کرده است. اکنون وزیر می‌خواهد این $n$ زمین را از اشراف خریداری کند و به روش زیر تقسیم کرده و به مردم بدهد. 1. زمین‌ها را به تعدادی بازه پشت سر هم افراز کند به طوری که مساحت زمین های همه بازه با هم برابر باشند. 2. مجموع قیمت‌ زمین های همه بازه ها با هم برابر باشند. 3. تعداد بازه ها بیشینه باشد. ![توضیح تصویر](http://uupload.ir/files/omwk_problem3.jpg) شما با اعلام کردن تعداد قسمت‌ها با شرایط فوق، به وزیر کمک کنید تا زمین‌ها را به مردم بدهد. # ورودی در خط اول ورودی یک عدد صحیح $n$ که برابر تعداد زمین ها است داده می شود. در خط بعدی $n$ عدد صحیح داده می شود که عدد $i$ام برابر $a_{i}$ است که همان قیمتی است که اشراف برای زمین $i$ام اعلام کردند. $$ 1 \leq n \leq 1\ 000\ 000 $$ $$1 \leq a_{i} \leq 1\ 000\ 000\ 000$$ # خروجی در یک خط خروجی بیشینه تعداد بازه ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 8 3 12 2 13 2 13 6 9 ``` ## خروجی نمونه ۱ ``` 4 ``` ## توضیح نمونه ۱ می‌توان این ۸ زمین را به ۴ بازه به مساحت ۲ افراز کرد بطوری که مجموع قیمت زمین‌های داخل هریک از ۴ بازه برابر ۱۵ شود: {3, 12}, {2, 13}, {2, 13}, {6, 9} ## ورودی نمونه ۲ ``` 4 1 1 1 1 ``` ## خروجی نمونه ۲ ``` 4 ```

وزیر و تقسیم زمین

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

وزیر شهر شکرستان می‌خواهد از $n$ نفر از اشراف، زمین کشاورزی بخرد و آن را به مردم بفروشد. همه‌ی زمین ها به شکل یک مربع $1 \times 1$ و کنار هم، در یک ردیف قرار دارند. هر یک از این اشراف برای زمین خودش یک قیمت به وزیر اعلام کرده است. اکنون وزیر می‌خواهد این $n$ زمین را از اشراف خریداری کند و به روش زیر تقسیم کرده و به مردم بدهد.

زمین‌ها را به تعدادی بازه پشت سر هم افراز کند به طوری که مساحت زمین های همه بازه با هم برابر باشند.
مجموع قیمت‌ زمین های همه بازه ها با هم برابر باشند.
تعداد بازه ها بیشینه باشد.

توضیح تصویر

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

ورودی🔗

در خط اول ورودی یک عدد صحیح $n$ که برابر تعداد زمین ها است داده می شود. در خط بعدی $n$ عدد صحیح داده می شود که عدد $i$ ام برابر $a_{i}$ است که همان قیمتی است که اشراف برای زمین $i$ ام اعلام کردند. $1 \leq n \leq 1\ 000\ 000$ $1 \leq a_{i} \leq 1\ 000\ 000\ 000$

خروجی🔗

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

مثال🔗

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

8
3 12 2 13 2 13 6 9

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

توضیح نمونه ۱🔗

می‌توان این ۸ زمین را به ۴ بازه به مساحت ۲ افراز کرد بطوری که مجموع قیمت زمین‌های داخل هریک از ۴ بازه برابر ۱۵ شود:

{3, 12}, {2, 13}, {2, 13}, {6, 9}

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

4
1 1 1 1

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- "کیا" عاشق "لیلی" شده و می‌خواهد برای "لیلی" یک دسته گل ببرد! برای این کار تصمیم گرفت از باغچه‌ی کنار خیابان که $n$ گل در یک ردیف دارد یک دسته گل بچیند. یک دسته گل شامل یک زیر مجموعه از گل‌های باغچه است. او می‌داند "لیلی" وقتی یک دسته گل را می‌پسندد که شرایط زیر را داشته باشد. 1. ارتفاع گل‌هایی که می‌چیند باید برابر باشد. 2. ارتفاع همه‌ی گل‌هایی که بین گل‌های انتخاب شده قرار دارد باید بیشتر یا مساوی ارتفاع گل‌های انتخاب شده باشد. 3. باید همه ی گل‌هایی را که می چیند به "لیلی" بدهد. (یعنی حق استفاده نکردن از گل چیده شده ای را ندارد.) ![توضیح تصویر](http://uupload.ir/files/tbpk_problem4.jpg) حال کیا می‌خواهد بیشترین تعداد گل را برای "لیلی" ببرد طوری که شرایط بالا را داشته باشد. "کیا" عاشق شده و نمی‌تواند این مسئله را حل کند. به او بگویید که او حداکثر چند گل می‌تواند برای "لیلی" ببرد. # ورودی در خط اول ورودی یک عدد صحیح $n$ و در خط بعدی $n$ عدد طبیعی داده می‌شود که عدد $i$ ام برابر ارتفاع گل $i$ام است. $$1 \leq n \leq 100\ 000$$$$1 \leq h_{i} \leq 1\ 000\ 000\ 000$$ # خروجی در یک خط خروجی بیشینه تعداد گلی که "کیا" می‌تواند برای "لیلی" ببرد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 8 9 8 3 8 ``` ## خروجی نمونه ۱ ``` 2 ``` ## توضیح نمونه ۱ کیا می‌تواند اولین و سومین گل را بچیند. او نمی‌تواند اولین، سومین و آخرین گل را بچیند؛ زیرا گلی با ارتفاع ۳ بین آخرین و سومین گل وجود دارد و از آن‌ها کوتاه‌تر است. ## ورودی نمونه ۲ ``` 2 8 2 ``` ## خروجی نمونه ۲ ``` 1 ```

کیا عاشق می‌شود

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

"کیا" عاشق "لیلی" شده و می‌خواهد برای "لیلی" یک دسته گل ببرد! برای این کار تصمیم گرفت از باغچه‌ی کنار خیابان که $n$ گل در یک ردیف دارد یک دسته گل بچیند. یک دسته گل شامل یک زیر مجموعه از گل‌های باغچه است. او می‌داند "لیلی" وقتی یک دسته گل را می‌پسندد که شرایط زیر را داشته باشد.

ارتفاع گل‌هایی که می‌چیند باید برابر باشد.
ارتفاع همه‌ی گل‌هایی که بین گل‌های انتخاب شده قرار دارد باید بیشتر یا مساوی ارتفاع گل‌های انتخاب شده باشد.
باید همه ی گل‌هایی را که می چیند به "لیلی" بدهد. (یعنی حق استفاده نکردن از گل چیده شده ای را ندارد.)

توضیح تصویر

حال کیا می‌خواهد بیشترین تعداد گل را برای "لیلی" ببرد طوری که شرایط بالا را داشته باشد. "کیا" عاشق شده و نمی‌تواند این مسئله را حل کند. به او بگویید که او حداکثر چند گل می‌تواند برای "لیلی" ببرد.

ورودی🔗

در خط اول ورودی یک عدد صحیح $n$ و در خط بعدی $n$ عدد طبیعی داده می‌شود که عدد $i$ ام برابر ارتفاع گل $i$ ام است.

$1 \leq n \leq 100\ 000$ $1 \leq h_{i} \leq 1\ 000\ 000\ 000$

خروجی🔗

در یک خط خروجی بیشینه تعداد گلی که "کیا" می‌تواند برای "لیلی" ببرد را چاپ کنید.

مثال🔗

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

5
8 9 8 3 8

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

توضیح نمونه ۱🔗

کیا می‌تواند اولین و سومین گل را بچیند. او نمی‌تواند اولین، سومین و آخرین گل را بچیند؛ زیرا گلی با ارتفاع ۳ بین آخرین و سومین گل وجود دارد و از آن‌ها کوتاه‌تر است.

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

2
8 2

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

+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روزی استادی وارد شهر شکرستان می‌شود. جمعی از دانش‌آموزان و دانش‌جویان نزد این استاد می‌روند و سوالات خود را از او می‌پرسند. "بهلول" نیز در میان دانش‌جویان نزد عالم می‌رود و سوال زیر را می‌پرسد : ![توضیح تصویر](http://uupload.ir/files/li18_problem5.jpg) اعداد زیبا اعدادی هستند که در نمایش مبنای $10$ آنها، ارقام $0$ و $1$ وجود نداشته باشد. اگر عدد $n$ عددی زیبا باشد $p(n)$ را تعریف می‌کنیم برابر ضرب ارقام در نمایش مبنای $10$ عدد $n$ است. اکنون $q(l, r)$ به این صورت تعریف می شود که چند عدد زیبا مانند $n$ وجود دارد به طوری که $l \leq p(n) \leq r$. به عبارت دیگر $q(l, r)$ برابر است با تعداد اعداد زیبایی که ضرب ارقام آن‌ها در بازه $[l, r]$ قرار می‌گیرد. برای اینکه "بهلول" کار استاد را سخت‌تر کند به او $t$ بازه $[l, r]$ می‌دهد تا استاد باقی مانده‌ی جواب مسئله را برای هریک از این بازه‌ها را به $10 ^ 9 + 7$ برای این سوال بدست آورد. اکنون استاد که از این سوال حیرت‌زده می‌شود از شما می‌خواهد به او کمک کنید تا جواب سوال فوق را به "بهلول" بدهد. # ورودی در خط اول ورودی یک عدد صحیح $t$ و در $t$ خط بعدی در هر خط دو عدد صحیح $l$ و $r$ به شما داده می شود. $$1 \leq t \leq 1\ 000\ 000$$$$1 \leq l \leq r \leq 1\ 000\ 000\ 000\ 000 $$ # خروجی خروجی $t$ سطر دارد که برای هر کدام از $t$ بازه‌‌ی ورودی باقی‌مانده‌ی پاسخ مساله را به $10^9 + 7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 10 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 ``` ## خروجی نمونه ۱ ``` 0 1 1 2 1 3 1 4 2 2 ``` ## ورودی نمونه ۲ ``` 10 5 10 2 3 9 10 3 8 5 10 4 6 2 3 3 5 1 7 1 10 ``` ## خروجی نمونه ۲ ``` 13 2 4 12 13 6 2 4 9 17 ```

استاد و بهلول

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

روزی استادی وارد شهر شکرستان می‌شود. جمعی از دانش‌آموزان و دانش‌جویان نزد این استاد می‌روند و سوالات خود را از او می‌پرسند. "بهلول" نیز در میان دانش‌جویان نزد عالم می‌رود و سوال زیر را می‌پرسد :

توضیح تصویر

اعداد زیبا اعدادی هستند که در نمایش مبنای $10$ آنها، ارقام $0$ و $1$ وجود نداشته باشد. اگر عدد $n$ عددی زیبا باشد $p(n)$ را تعریف می‌کنیم برابر ضرب ارقام در نمایش مبنای $10$ عدد $n$ است.

اکنون $q(l, r)$ به این صورت تعریف می شود که چند عدد زیبا مانند $n$ وجود دارد به طوری که $l \leq p(n) \leq r$ . به عبارت دیگر $q(l, r)$ برابر است با تعداد اعداد زیبایی که ضرب ارقام آن‌ها در بازه $[l, r]$ قرار می‌گیرد.

برای اینکه "بهلول" کار استاد را سخت‌تر کند به او $t$ بازه $[l, r]$ می‌دهد تا استاد باقی مانده‌ی جواب مسئله را برای هریک از این بازه‌ها را به $10 ^ 9 + 7$ برای این سوال بدست آورد. اکنون استاد که از این سوال حیرت‌زده می‌شود از شما می‌خواهد به او کمک کنید تا جواب سوال فوق را به "بهلول" بدهد.

ورودی🔗

در خط اول ورودی یک عدد صحیح $t$ و در $t$ خط بعدی در هر خط دو عدد صحیح $l$ و $r$ به شما داده می شود.

$1 \leq t \leq 1\ 000\ 000$ $1 \leq l \leq r \leq 1\ 000\ 000\ 000\ 000$

خروجی🔗

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

مثال🔗

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

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- "بیا" تصمیم گرفته است که از شکرستان به نمکستان سفر کند. او می‌داند که در این حوالی $n$ شهر با شماره‌های ۱ تا $n$ (شکرستان شهر شماره ۱ و نمکستان شهر شماره $n$) و $m$ جاده دو طرفه بین این شهرها وجود دارد. می‌دانیم بین هر دو شهر حداکثر یک جاده قرار دارد و برای هر جاده می‌دانیم طی کردن آن چقدر طول می‌کشد. او نمی‌خواهد در سفر خود از یک شهر دو بار عبور کند. ![توضیح تصویر](http://uupload.ir/files/jsxm_problem6.jpg) به تازگی دانشمندان شکرستان سیستم ارتباطی عجیبی به نام "بدو بیا" در بعضی از این $n$ شهر راه انداختند. این سیستم به این صورت کار می‌کند که اگر یک شهر دارای این سیستم باشد می‌تواند پس از $t$ ثانیه از یک شهر به یک شهر دیگر که دارای این سیستم است برود. قسمت عجیب این سیستم اینجاست که ممکن است، این عدد $t$ منفی باشد! در صورتی که می تواند چنین سفری را انجام دهد، حداقل زمانی که طول می‌کشد تا از شکرستان به نمکستان سفر کند چقدر است؟ (عجیب است که این مقدار نیز می‌تواند منفی باشد!) # ورودی در سطر اول ورودی سه عدد $n$ و $m$ و $t$ آمده است که به ترتیب نمایانگر تعداد شهرها ، جاده‌ها و مقدار $t$ هستند. شکرستان شهر شماره 1 و نمکستان شهر شماره $n$ است. در سطر دوم یک رشته با $n$ حرف آمده‌است که $i$امین حرف آن برابر ۱ است اگر و تنها اگر در راس شماره $i$ سیستم ارتباطی "بدو بیا" وجود داشته باشد و در غیر این صورت $i$امین حرف رشته برابر ۰ است. سپس در $i$امین سطر از هریک از $m$ سطر بعدی سه عدد $u_i$ و $v_i$ و $w_i$ آمده‌اند که دو شهر انتهایی و زمان طی کردن جاده بین این دو شهر را نشان می‌دهد. در ورودی‌های این سوال تضمین می‌شود که بین هر دو شهر حداکثر یک جاده از این $m$ جاده موجود است و دو شهر انتهایی یک جاده یکسان نیستند. $$ 2 \le n \le 1\ 000 $$ $$1 \le m \le 1\ 000$$ $$ 1 \le u_i, v_i \le n $$ $$|t| \le 1\ 000\ 000$$ $$ 1 \le w_i \le 1\ 000\ 000 $$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین زمانی است که طول می‌کشد تا از شکرستان به نمکستان سفر کند. در صورتی که نمی‌تواند چنین سفری را انجام دهد، کلمه‌ی $"Impossible"$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 3 101 1 2 2 2 3 2 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 4 4 -6 0110 1 2 2 2 3 2 3 4 2 1 4 1 ``` ## خروجی نمونه ۲ ``` -2 ``` ## ورودی نمونه ۳ ``` 4 2 10 1000 1 2 1 2 3 1 ``` ## خروجی نمونه ۳ ``` Impossible ```

سفر بیا

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

"بیا" تصمیم گرفته است که از شکرستان به نمکستان سفر کند. او می‌داند که در این حوالی $n$ شهر با شماره‌های ۱ تا $n$ (شکرستان شهر شماره ۱ و نمکستان شهر شماره $n$ ) و $m$ جاده دو طرفه بین این شهرها وجود دارد. می‌دانیم بین هر دو شهر حداکثر یک جاده قرار دارد و برای هر جاده می‌دانیم طی کردن آن چقدر طول می‌کشد. او نمی‌خواهد در سفر خود از یک شهر دو بار عبور کند.

توضیح تصویر

به تازگی دانشمندان شکرستان سیستم ارتباطی عجیبی به نام "بدو بیا" در بعضی از این $n$ شهر راه انداختند. این سیستم به این صورت کار می‌کند که اگر یک شهر دارای این سیستم باشد می‌تواند پس از $t$ ثانیه از یک شهر به یک شهر دیگر که دارای این سیستم است برود. قسمت عجیب این سیستم اینجاست که ممکن است، این عدد $t$ منفی باشد!

در صورتی که می تواند چنین سفری را انجام دهد، حداقل زمانی که طول می‌کشد تا از شکرستان به نمکستان سفر کند چقدر است؟ (عجیب است که این مقدار نیز می‌تواند منفی باشد!)

ورودی🔗

در سطر اول ورودی سه عدد $n$ و $m$ و $t$ آمده است که به ترتیب نمایانگر تعداد شهرها ، جاده‌ها و مقدار $t$ هستند. شکرستان شهر شماره 1 و نمکستان شهر شماره $n$ است.

در سطر دوم یک رشته با $n$ حرف آمده‌است که $i$ امین حرف آن برابر ۱ است اگر و تنها اگر در راس شماره $i$ سیستم ارتباطی "بدو بیا" وجود داشته باشد و در غیر این صورت $i$ امین حرف رشته برابر ۰ است.

سپس در $i$ امین سطر از هریک از $m$ سطر بعدی سه عدد $u_i$ و $v_i$ و $w_i$ آمده‌اند که دو شهر انتهایی و زمان طی کردن جاده بین این دو شهر را نشان می‌دهد.

در ورودی‌های این سوال تضمین می‌شود که بین هر دو شهر حداکثر یک جاده از این $m$ جاده موجود است و دو شهر انتهایی یک جاده یکسان نیستند. $2 \le n \le 1\ 000$ $1 \le m \le 1\ 000$ $1 \le u_i, v_i \le n$ $|t| \le 1\ 000\ 000$ $1 \le w_i \le 1\ 000\ 000$

خروجی🔗

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

مثال🔗

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

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

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

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

-2

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

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

Impossible