Недавно археологической командой «Раскопай» были обнаружены остатки древней цивилизации. Особое внимание привлекла карта с месторасположением народов, живших в то время. Карта представляет собой прямоугольный лист, разлинованный горизонтальными линиями на M полос и вертикальными линиями на N столбцов. Таким образом формируются M*N клеток — древних поселений, которые заселялись сообществами. В каждой клетке этой карты написано натуральное число — идентификатор народа, к которому принадлежит это сообщество людей (рукопись с соответствием между идентификаторами и народами также была обнаружена).

Чтобы объяснить этот процесс введем систему координат на карте так, что границы карты параллельны осям координат. Пусть координаты (0,0) соответствуют самой верхней левой клетке, а (N–1, M–1) — самой нижней правой. Переселение народов проходит в несколько этапов. Опишем как проходит каждый этап.

Назовем квадратом множество всех поселений с координатами (x,y) такими, что x₁≤x≤x₂, y₁≤y≤y₂, где x₂–x₁=y₂–y₁. Соответственно клетка (x₁,y₁) является левой верхней клеткой квадрата, (x₂,y₂) —нижней правой.

На каждом этапе переселения переселяются сообщества внутри некоторого квадрата по следующему правилу. Если переселение происходит внутри квадрата, левой верхней клеткой которого является клетка (x₁,y₁), а правой нижней — (x₂,y₂), то сообщество, проживавшее в поселении с координатами (x,y) (x₁≤x≤x₂, y₁≤y≤y₂) переселяется в поселение с координатами (x₂–(y₂–y),y₂–(x₂–x)), при этом, возможно, что некоторые сообщества остаются на своих местах. Все сообщества, живущие вне квадрата, в котором происходит переселение, остаются на своих местах.

Историки из «Разузнай» хотят для подтверждения (или опровержения) своей теории переселений проверить, могла ли в результате таких переселений из карты, которая есть в распоряжении «Разузнай» получиться карта, которую нашли археологи. Помогите им — напишите программу, которая будет это делать.

Папа Васи очень заботится об образовании сына. Особое значение он придает иностранным языкам. Недавно они приступили к изучению английского. Чтобы ускорить процесс, папа разговаривает с Васей исключительно на нем. Разумеется, это создает некоторые трудности при общении. Каждый раз, когда Вася что-нибудь скажет, папе приходится долго гадать, что именно он имел в виду.

Папа знает словарный запас сына. Считается, что Вася мог иметь в виду словарное слово P, если оно входит как подпоследовательность в слово T (то, что он сказал). Другими словами, если существует такая возрастающая последовательность индексов i₁ < i₂ < ... < i_m (где m — длина P), что P[j] = T[i_j] для всех j = 1..m.

Вам дается словарный запас Васи и сказанное им слово. Для каждого словарного слова надо определить, мог ли Вася иметь его в виду.

В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».

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

Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.

Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.

Напишите программу, которая определит, есть ли у мухи шанс спастись, и если есть, то выведет, что должна муха для этого делать.