+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** سروش در ابتدای صف ورود به سالن سینما، منتظر یکی از دوستانش است. دوست سروش در انتهای صف ایستاده و به دنبال او می‌گردد. به جز سروش و دوست او، $n$ نفر دیگر در صف، بین آن دو، ایستاده‌اند که از ابتدای صف به ترتیب با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند. با توجه به اینکه تمام این افراد صرفاً برای گذراندن وقت به سینما آمده بودند، تصمیم گرفتند به جای دیدن فیلم، کاری کنند که سروش و دوستش نتوانند یک‌دیگر را ببینند. در هر لحظه تمامی افراد درون صف در یک جهت نگاه می‌کنند. جهت نگاه تمامی افراد در هر ثانیه یا به سمت سروش و ابتدای صف است و یا به سمت دوست او و انتهای صف. در هر ثانیه هر فرد اگر در راستایی که نگاه می‌کند، فرد دیگری که در حال حاضر از او اکیداً بلندتر باشد ببیند، قدش را به اندازه‌ی یک سانتی‌متر افزایش می‌دهد. علی به مدت $m$ ثانیه این صحنه را نگاه می‌کند و به ازای هر یک از ثانیه‌ها جهت نگاه افراد را یادداشت می‌کند. به عبارت دقیق‌تر او به ازای هر عملیات یک حرف انگلیسی یادداشت می‌کند که اگر برابر L باشد افراد در ثانیه‌ی $i$ ام به سمت سروش و ابتدای صف نگاه می‌کنند و در صورتی که برابر R باشد، افراد در این ثانیه به سمت دوست سروش و انتهای صف نگاه می‌کنند. او قد تمامی $n$ نفر را پیش از شروع عملیات‌های گفته شده، می‌داند. به عبارت دقیق‌تر، او می‌داند که قد نفر $i$ ام پیش از شروع عملیات‌ها $h_i$ سانتی‌متر است. برنامه‌ای بنویسید که با داشتن قد ابتدایی و جهت نگاه افراد در هر ثانیه، قد نهایی هر فرد را محاسبه کند. # ورودی در خط اول ورودی دو عدد طبیعی $n$، تعداد افراد درون صف، و $m$، تعداد ثانیه‌هایی که علی عملیات گفته شده را مشاهده کرده، آمده است. در خط دوم ورودی $n$ عدد $h_1, h_2, \ldots, h_n$ آمده است که قد ابتدایی افراد را نشان می‌دهند. در خط سوم ورودی یک رشته‌ی به طول $m$ از حروف ‌R و L آمده است که حرف $i$ام این رشته، حرف نوشته‌ شده در ثانیه $i$ام را نشان می‌دهد. # خروجی در تنها خط خروجی $n$ عدد چاپ کنید که عدد $i$ام قد نهایی فرد $i$ام را نشان می‌دهد. $$ 1 \le n, m \le 200 \ 000 $$ $$ 0 \le h_i \le 10^9 $$ # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:------------------:|:------------------:|:------------------:| | ۱ | ۱۰۰ |بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 5 2 1 3 1 3 1 RL ``` ## خروجی نمونه ۱ ``` 2 3 3 3 2 ``` ## ورودی نمونه ۲ ``` 5 4 5 4 3 2 1 LLRL ``` ## خروجی نمونه ۲ ``` 5 5 5 5 4 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** بازی Pokemon Go در مدت کوتاهی به محبوب‌ترین بازی کشور هکر‌ها تبدیل شده است! با اینکه هکرها به Pokemon Go بسیار علاقه دارند اما همچنان جذاب‌ترین کار برای آن‌ها هک کردن است. ولادمیر لوین (Vladimir Levin)، یکی از خطرناک‌ترین هکر‌های شهر، تعدادی از سرور‌های Pokemon Go را هک کرده و برنامه‌ی تلفن همراه XPokemon را نوشته است که یکی از قابلیت‌های آن اعلام فاصله‌ی دورترین PokeStop از مکان فعلی شخص است. لازم به ذکر است که در کشور هکر‌ها، شهرها و جاده‌های بین آن‌ها‌ تشکیل یک درخت می‌دهند و PokeStop ها همواره در داخل شهر‌ها قرار دارند. کوین میتنیک (Kevin Mitnick)، رقیب قدیمی ولادیمیر، در جدید ترین پروژه‌ی خود موفق به هک کردن تلفن‌های همراه ساکنین برخی از شهر‌ها شده است. کوین از طریق این تلفن‌های همراه هک شده به خروجی برنامه Xpokemon دست یافته و می‌خواهد مکان PokeStop ها را بیابد. کوین برای پیدا کردن مکان PokeStop ها نیاز به کمک شما دارد و به همین منظور اطلاعات به دست آمده را با شما به اشتراک گذاشته است. او به ازای هر شهر‌ مانند $v$ که موفق به هک کردن تلفن‌های همراه ساکنین آن شده است، عدد $d$ را، که فاصله‌ی آن شهر با دورترین PokeStop از آن را نشان می‌دهد، به شما داده است. منظور از فاصله بین دو شهر، کمترین تعداد جاده لازم برای رسیدن از شهر اول به شهر دوم است. به کوین کمک کنید و با توجه به اطلاعاتی که در اختیار دارید، مکان PokeStop ها را حدس بزنید. یک حدس معتبر نباید با اطلاعات داده‌شده تناقضی داشته باشد. در صورتی که هیچ حدس معتبری وجود نداشت، اعلام کنید که اطلاعات داده شده نادرست می‌باشد. # ورودی در خط اول ورودی، دو عدد $n$ و $q$ آمده است که به ترتیب تعداد کل شهر‌‌ها و تعداد شهر‌هایی که کوین موفق به هک کردن تلفن‌های همراه ساکنین آن شده است را نشان می‌دهند. در هر یک از $n-1$ خط بعدی در هر خط دو عدد طبیعی $v$ و $u$ آمده است که نشان‌دهنده‌ی وجود یک جاده بین این دو شهر است. در هر یک از $q$ خط بعدی دو عدد $v$ و $d$ آمده است که نشان می‌دهد فاصله دورترین PokeStop از شهر $v$ برابر $d$ است. **تضمین می‌شود گراف ورودی درخت است و به ازای هر شهر حداکثر یک بار اطلاعات داده می‌شود.** $$ 1 \le q \le n \le 200 \ 000 $$ # خروجی در صورتی که هیچ حدس معتبری وجود ندارد، در تنها خط خروجی عدد $-1$ را چاپ کنید. در غیر این‌ صورت، در تنها خط خروجی حدس خود که شامل یک رشته‌ی $n$ حرفی از 0 و 1 می‌شود را چاپ کنید. 0 بودن حرف ‌$i$ام رشته به این معناست که در شهر $i$ام PokeStop ای وجود ندارد و 1 بودن آن به این معناست که در شهر $i$ام PokeStop وجود دارد. در صورتی که چند جواب برای ورودی داده شده وجود دارد می‌توانید هر کدام را که خواستید چاپ کنید. # زیرمسئله‌ها | زیرمسئله | شماره‌ی تست‌ها| نمره | محدودیت |:------------------:|:--------:|:----------:|:------------------:| | ۱ | ۱ تا ۱۱ | ۱۰ | $ n \le 15 $ | | ۲ | ۱۲ تا ۲۴ | ۲۰ | $ n \le 200 $ | | ۳ | ۲۵ تا ۳۴ | ۲۵ | $ n = q $ | | ۴ | ۳۵ تا ۶۴ | ۴۵ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 4 1 2 1 3 1 4 1 5 2 2 3 2 4 2 5 2 ``` ## خروجی نمونه ۱ ``` 01111 ``` ## ورودی نمونه ۲ ``` 3 3 1 2 2 3 1 0 2 1 3 0 ``` ## خروجی نمونه ۲ ``` -1 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** مورتی بار دیگر در یک ماجراجویی خطرناک با پدربزرگ دانشمندش ریک همراه شده تا از یک نانوایی معروف به نام «سلری» برای صبحانه نان تهیه کنند. این نانوایی در دنیای دوردستی واقع شده است که ساکنان بی‌حوصله‌ای دارد. آن‌ها تا زمانی که حوصله‌شان به سر نیامده موجودات مهربانی هستند، اما به محض این که حوصله‌شان سر برود تبدیل به موجودات بی‌رحمی می‌شوند و هر چیزی در اطرافشان باشد را به آتش می‌کشند. «آقای میسیک»، صاحب نانوایی سلری، که از دوستان قدیمی ریک و مورتی است، امروز دست‌تنها است و مشتری‌های زیادی در صف نانوایی منتظر نان‌شان هستند. او با دیدن ریک و مورتی بسیار خوش‌حال می‌شود و از آن‌ها می‌خواهد در امر خطیر نان‌پزی کمکش کنند. آن‌ها به این شکل تقسیم وظیفه می‌کنند که ریک و آقای میسیک نان‌ها را بپزند و مورتی نان‌ها را بین مشتری‌ها پخش کند. طبق معمول مشتری‌ها در $n$ صف مختلف در نانوایی ایستاده اند. مورتی هر نانی را که به دستش می‌رسد را می‌تواند به یکی از مشتری‌هایی که در سر یکی از صف‌ها ایستاده است بفروشد. به بیان دیگر او هر بار یکی از $n$ صف را انتخاب می‌کند و به مشتری‌ای که در جلوی آن صف ایستاده نان می‌فروشد. هر مشتری دقیقاً به یک عدد نان نیاز دارد و بعد از خرید نان از صف خارج می‌شود و مغازه را ترک می‌کند. آقای میسیک و ریک با کمک یک‌دیگر می‌توانند با سرعت یک نان بر ثانیه نان بپزند. از طرفی، هر مشتری یک میزان حوصله‌ای دارد که برای مشتری $j$ ام در صف $i$ ام آن را با $p_{i,j}$ نشان می‌دهیم. در صورتی که این مشتری تا $p_{i,j}$ ثانیه بعد از شروع به کار ریک و مورتی نان نخرد، نانوایی را به آتش می‌کشد.  در صورت آتش گرفتن مغازه ریک و مورتی می‌توانند با استفاده از دستگاه تله‌پورت فرار کنند و هیچ آسیبی نبینند. اما مورتی از کار نان فروشی لذت می‌برد و دوست دارد تا قبل از آتش گرفتن مغازه یا تمام شدن مشتری‌ها، به بیشترین تعداد مشتری ممکن نان بفروشد. مورتی حداکثر چند نان می‌تواند بفروشد؟ دقت کنید که بعد از شروع به کار ریک و مورتی مشتری دیگری وارد مغازه نخواهد شد. # ورودی در خط اول ورودی $n$، تعداد صف‌های نانوایی، آمده است. در $n$ خط بعدی در هر خط ابتدا یک عدد طبیعی $l_i$ آمده است که نشان‌دهنده‌ی طول صف $i$ ام است. در ادامه‌ی خط $i$ ام، $l_i$ عدد طبیعی آمده است که نشان‌دهنده‌ی $p_{i,1}, p_{i,2}, ..., p_{i,l_i}$، میزان حوصله‌ی مشتری‌های صف $i$ است. $$ 1 \le n \le \sum_{i=1}^n{l_i} \le 100 \ 000 $$ $$ 1 \le p_{i,j} \le 10^9 $$ # خروجی در تنها خط خروجی بیشترین تعداد مشتری‌هایی که مورتی می‌تواند به آن‌ها نان بفروشد را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | شماره‌ی تست‌ها| نمره | محدودیت |:------------------:|:--------:|:----------:|:------------------:| | ۱ | ۱ تا ۱۷ | ۱۰ | $ \sum_{i=1}^n{l_i} \le 10 $ | | ۲ | ۱۸ تا ۳۵ | ۲۰ | $ \sum_{i=1}^n{l_i} \le 1000 ,n\le2 $ | ۳ | ۳۶ تا ۸۵ | ۷۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 2 1 1 2 9 2 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 3 2 1 2 2 3 5 1 4 ``` ## خروجی نمونه ۲ ``` 5 ``` ## ورودی نمونه ۳ ``` 3 1 3 1 4 2 5 2 ``` ## خروجی نمونه ۳ ``` 4 ```