При обработке изображений часто встречается такая задача, когда нужно изменить размер изображения так, чтобы оно “вписалось” в заданный прямоугольник. То есть исходное изображение уменьшается (или увеличивается) таким образом, что одна из его сторон становится точно равной соответствующей стороне заданного прямоугольника, а вторая сторона подбирается так, чтобы соотношение сторон получившегося изображения было как можно ближе к оригиналу. При этом размеры получившегося изображения должны быть наибольшими возможными, но не должны при этом превышать размеры прямоугольника. Также, все размеры должны быть целыми положительными числами.
Вам заданы размеры исходного изображения и размеры прямоугольника, в который это изображение нужно вписать. Вычислите, какими должны быть размеры вписанного изображения. Учтите, что поворачивать изображение или прямоугольник нельзя!

Входные данные

Входной файл содержит 4 целых числа $A$,$B$,$C$,$D$ ($1 ≤ A,B,C,D ≤ 10^9$), где $A$ и $B$ — ширина и высота исходного изображения, а $C$ и $D$ — ширина и высота прямоугольника, в который изображение нужно вписать.

Выходные данные

Выведите 2 целых числа: ширину и высоту обработанного изображения.

Примеры:

Вход:

1280 720 640 480

Ответ:

640 360

Вход:

640 480 1280 720

Ответ:

960 720

Оценивание:

В 50% тестов: A,B,C,D ≤ 1000 В 75% тестов: A, B, C, D ≤ 1000000

Вам дана таблица $N × M$ , в каждой ячейке которой написана какая-то цифра. Будем считать, что число есть в этой таблице, если его можно “прочитать” в каком-то месте этой таблицы по горизонтали, по вертикали или по диагонали (вправо, вниз, или вправо-вниз).
Найдите количество и сумму всех простых чисел, состоящих не более чем из 6 цифр, которые есть в этой таблице. Если какое-то число повторяется несколько раз в разных местах таблицы, то все эти вхождения нужно учитывать. Числа не должны начинаться с нуля.

Входные данные

Первая строка входного файла содержит два целых числа $N$ и $M$ ($1 ≤ N, M ≤ 1500$). Следующие $N$ строк содержат по $M$ цифр, разделенных пробелом.

Выходные данные

Выведите два целых числа: количество и сумму всех найденных простых чисел.

Примеры:

Вход:

4 5 
1 2 3 4 5 
6 7 8 9 0 
0 9 8 7 6 
5 4 3 2 1

Ответ:

19 1547

Примечание:

Найденные простые числа (некоторые встречаются несколько раз): 2, 2, 3, 3, 5, 5, 7, 7, 17, 23, 43, 61, 67, 79, 83, 89, 97, 883. В 50% тестов $N, M ≤ 100$.

Многие математические игры кажутся довольно странными для посторонних. Вот пример одной из них.
У вас имеется 2N − 1 карточек. Вначале в игре участвуют N карточек. На лицевой стороне каждой из них написано какое-то целое число. На обратной стороне этих же карточек написан 0 (ноль). Остальные N −1 карточек пустые с обеих сторон и пока не участвуют в игре. Вы загадываете какое-то число от 1 до N. Каждый ход игры игры заключается в следующих действиях:

• выбрать карточку с наименьшим числом на лицевой стороне. Если таких карточек несколько — выбрать ту, на обратной стороне которой число минимально. Пусть выбрана карточка с числом A на лицевой стороне и B на обратной стороне. Убрать эту карточку из игры.
• еще раз выбрать карточку с наименьшим числом на лицевой стороне. Если таких карточек несколько — выбрать ту, на обратной стороне которой число минимально. Пусть выбрана карточка с числом C на лицевой стороне и D на обратной стороне. Убрать эту карточку из игры.
• взять пустую карточку. На лицевой стороне написать число, равное A + C, а на обратной — максимальное из чисел B + 1 и D + 1. Добавить эту карточку в игру.

Игра заканчивается через N − 1 ход, когда в игре останется только одна карточка. Если число, которое вы загадали в начале, совпадает с числом, которое написано на обратной стороне оставшейся карточки, то вы выиграли. Иначе — вы проиграли.
Напишите программу, которая по исходному состоянию игры определяет число, которое будет написано на обратной стороне последней карточки.

Входные данные

Первая строка входного файла содержит число $N$ ($1 ≤ N ≤ 105$). Следующая строка содержит $N$ целых чисел — числа, написанные на лицевой стороне карточек. Каждое число лежит в промежутке от $−10^9$ до $10^9$ включительно.

Выходные данные

Выведите одно целое число — ответ к задаче.

Примеры:

Вход:

5 
1 2 3 4 5

Ответ:

3

Примечание:

Описание ходов игры: исходное состояние: (1 0), (2 0), (3 0), (4 0), (5 0) после хода 1: (3 1), (3 0), (4 0), (5 0)
после хода 2: (6 2), (4 0), (5 0)
после хода 3: (6 2), (9, 1)
после хода 4: (15, 3)
В 50% тестов $N ≤ 1000$.

Натуральное число называется если читается слева направо и справа налево одинаково. Вам дано одно натуральное число $N$, которое состоит из не более чем $10^6$ цифр. Найдите наименьший палиндром, который строго больше $N$.

Входные данные

В единственной строке входного файла содержится одно натуральное число $N$. $N$ не содержит лидирующих нулей и состоит из не более чем $10^6$ цифр.

Выходные данные

Выведите одно целое число – наименьший палиндром, который строго больше N.

Примеры:

Вход:

365

Ответ:

373

Вход:

999999

Ответ:

1000001