Около полугода назад было доказано, что проверка возможности прохождения уровня в классической игре Super Mario Bros. лежит в классе сложности PSPACE и, более того, является PSPACE -полной задачей. Мы не предлагаем вам понять, что это значит, но предлагаем почувствовать, насколько сложно бывает программно играть в компьютерные игры. Для этого мы опишем упрощённый вариант игры и предложим проверить, возможно ли пройти уровень в нашем варианте «Марио» или нет (для понимания задачи необязательно быть знакомым с оригинальной игрой).

Наш вариант игры происходит на клетчатом поле, состоящем из n строк на m столбцов. Каждая клетка поля может принадлежать одному из следующих видов:

• пустая клетка, обозначается символом подчёркивания ' _ ';
• клетка с землёй, обозначается решёткой ' # ';
• клетка, содержащая монетку, обозначается строчной английской буквой ' c ';
• клетка, в которой находится Марио, обозначается строчной английской буквой ' m ';
• клетка, в которой находится Принцесса, обозначается строчной английской буквой ' p '.

Пронумеруем строки сверху вниз числами от 1 до n и столбцы слева направо целыми числами от 1 до m . Где-то в m -м столбце находится Принцесса (в клетке, обозначенной буквой ' p '). А в одной из клеток первого столбца стоит Марио (в клетке, обозначенной ' m '). Конечно, и Принцесса, и Марио стоят на земле, то есть в клетках, под каждым из них находится земля.

Также в некоторых столбцах от второго до ( m - 1) -го, возможно, находятся монетки. В одном столбце находится не более одной монетки, а также любая монетка лежит на земле, то есть в клетке под монеткой обязательно находится земля.

Марио, как и в классическом варианте игры, нужно добраться до Принцессы, но еще ему необходимо собрать все монетки, которые есть на поле. Марио может перемещаться только посредством прыжков.

Прыжок Марио состоит из двух частей: сначала он летит вертикально вверх, а потом горизонтально вправо. Вертикальная часть прыжка может иметь длину y от 0 до a клеток, а горизонтальная может иметь длину x от 0 до b клеток. В частности, Марио может прыгнуть вертикально вверх, не перемещаясь по горизонтали, а также прыгнуть горизонтально вправо, не смещаясь при этом по вертикали. Естественно, Марио не может пролетать сквозь клетки, содержащие землю. Обратите внимание, в отличие от оригинальной игры Марио не может перемещаться влево.

Если после окончания прыжка Марио оказывается в клетке, под которой нет земли, он падает вниз, пока под ним не окажется земля. В случае, если Марио долетает до n -й (самой нижней) строки, он проваливается вниз за экран и погибает, а игра заканчивается. Также Марио не может выпрыгивать за границы поля сверху или справа.

Если Марио оказывается в клетке с монеткой (возможно, в процессе прыжка), то он её подбирает.

Определите, возможно ли добраться до клетки с Принцессой, подобрав все монетки.

Ивану с детства нравились газеты. У него даже была мечта стать главным редактором газеты. Однажды ему представился шанс осуществить свою мечту. Чтобы устроиться на работу в издательство, ему необходимо выполнить тестовое задание — сверстать рекламное объявление.

Задано поле шириной \(W\) и высотой \(H\). Объявление должно состоять из одной или нескольких строк, в которых необходимо разместить в заданном порядке \(N\) слов. Про \(i\)-е слово известно, что при печати в стандартном масштабе оно занимает прямоугольник шириной \(a_i\) и высотой \(b_i.\)

Чтобы объявление выглядело красиво, все слова в нем должны быть напечатаны в одном масштабе. При печати в масштабе \(k\) размеры всех слов умножаются на \(k\). Если исходно слово занимало прямоугольник \(a_i \times b_i\) , то при печати в масштабе \(k\) оно занимает прямоугольник размером \((k \cdot a_i) \times (k \cdot b_i)\). Кроме того, если в строке более одного слова, то все слова в ней должны иметь одинаковую высоту. Разумеется, ни одно слово не должно выходить за границы поля.

На рисунке приведен пример красивого объявления с тремя словами.

Иван живет в небольшом симпатичном домике в деревне. Вдоль его участка расположен забор, который недавно был выкрашен в красный цвет. Но тут в деревню к Ивану пришла цивилизация в лице рекламного агента, расклеивающего всюду свои объявления. И его забор постигла та же участь.

Каждый день на его забор приклеивают новое объявление. Таким образом за последние \(n\) дней на забор наклеено уже \(n\) объявлений и Ивану кажется, что рекламой заклеен уже весь забор, состоящий из \(m\) досок. Доски пронумерованы вдоль забора от \(1\) до \(m\).

Оказалось, что в каждый из \(n\) дней когда приходил рекламный агент и приклеивал объявление, сосед Ивана Петр записывал, какие доски оказывались заклеены этим объявлением. А именно, выяснилось что в \(i\)-й день очередное объявление было наклеено таким образом, что занимало доски с \(l_i\)-й по \(r_i\)-ю включительно. При этом рекламный агент вполне мог заклеить новым объявлением полностью или частично свое же собственное объявление.

Для составления жалобы в администрацию деревни Ивану необходимо удостовериться, что рекламой заклеен весь забор. Помогите ему выяснить, так ли это.

Байтландия готовится к военным учениям. Это очень важное мероприятие, даже министр обороны Байтландии контролирует организацию учений на месте. Министр обороны обеспокоен тем, как же пройдут учения танков.

Байтландия состоит из островов, некоторые из которых соединены мостами. Каждый мост соединяет два различных острова, любые два острова соединены напрямую не более чем одним мостом. Байтландцы очень экономный народ, поэтому на каждый остров ведут не более двух мостов.

План мероприятия еще не готов, но известно, что план учений танков будет таким: танки должны будут проехать с одного острова на другой, пользуясь некоторыми мостами, причем не важно, какими именно мостами будут пользоваться танки. В Байтландии много мостов, которые были построены много лет назад и для танков совершенно не предназначены. Поэтому министр обороны решил укрепить некоторые мосты. А конкретно, он хочет укрепить несколько мостов так, чтобы вне зависимости от плана учений, выполнялось условие: если была возможность переехать с острова \(u\) на остров \(v\), то после укрепления некоторых мостов можно переехать с острова \(u\) на остров \(v\) по укрепленным мостам. При этом укрепление моста — дорогая операция, поэтому министр хочет укрепить минимальное число мостов.

Министр обороны Байтландии хочет знать, сколько существует различных способов укрепления минимального числа мостов. Два способа считаются различными, если существует мост, который укреплен в одном из способов и не укреплен в другом. Помогите министру обороны найти ответ на волнующий его долгое время вопрос. Поскольку ответ может быть довольно большим, выведите его по модулю \(10^9 \ + \ 7\).

Лягушонок Билли сидел на камне и любовался на закат, когда понял, что проголодался. Он огляделся и с удивлением обнаружил, что в ручье около него копошатся мошки. Ручей представляет собой прямую, на которой расположен и камень, на котором сидит Билли. Лягушонок был очень голоден, и потому захотел съесть всех мошек. У Билли очень длинный язык, поэтому он может, не спрыгивая с камня, съесть любую мошку (но только одну за раз).

Однако высовывать язык на большие расстояния не так-то просто, лягушонок на каждый сантиметр высунутого языка тратит одну единицу энергии. Каждый раз, когда Билли съедает мошку из какой-то точки происходит следующее: все мошки, сидящие слева от съеденной мошки, и все мошки, сидящие справа от нее в ужасе отпрыгивают от места событий на один сантиметр вдоль ручья. Мошки, которые сидят в той же точке, что и съеденная, настолько шокированы этим событием, что не двигаются.

Лягушонок Билли хочет понять — какое минимальное количество единиц энергии ему потребуется для того, чтобы съесть всех мошек. Помогите ему это выяснить.