Задача A. Заплыв ≡

Условие

Оксана любит плавать и готовится к заплыву через Амурский залив. Для подготовки она каждый день приходит в бассейн и проводит там несколько часов, переплывая от одного края бассейна до другого. Длина бассейна, где занимается Оксана — N метров. Она успевает пересечь его за M секунд, и ещё K секунд тратит на разворот. Сколько метров Оксана успеет проплыть за L минут?

Формат входного файла

Первая строка входного файла содержит четыре натуральных числа: N M K L.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество проплытых метров.

Ограничения

1 ≤ N, M, K, L ≤ 1000

Примеры тестов

25 76 2 45

865

50 50 1 60

3530

Задача B. Битовая Золушка ≡

Условие

Каждый год в конце октября в королевстве Л. проходит торжественный бал, посвящённый Последнему Тёплому Дню. Золушка весь год мечтала попасть на бал, однако в последний момент мачеха подкинула ей задачу: рассортировать огромный мешок перемешавшихся нулей и единиц. На перебор цифр вручную может уйти несколько часов, и тогда Золушка гарантированно опоздает к началу праздника.

Помогите Золушке успеть на бал вовремя и напишите программу, которая рассортирует цифры за неё.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

Формат входного файла

Первая строка входного файла содержит натуральное число N — количество тестов в файле. Последующие N строк содержат последовательности, состоящие из M_N символов «0» и K_N символов «1» в произвольном порядке.

Формат выходного файла

Выходной файл должен содержать N строк: каждая строка должна содержать последовательность из M_N символов «0» и последовательность из K_N символов «1». Последовательности должны быть разделены единственным символом «пробел» (код 32).

Ограничения

1 ≤ N ≤ 100, 1 ≤ M_N + K_N ≤ 300, M_N, K_N ≥ 0

Примеры тестов

2
0011101000101
11111110

0000000 111111
0 1111111

Задача C. Межпланетные гармонии ≡

Условие

Обитатели планеты Бемоль недавно обнаружили, что соседняя планета, Диез, также населена разумными существами. Предварительные попытки коммуникации показали, что жители планеты Диез наиболее охотно идут на контакт, если информация передаётся им в виде музыкальных произведений, исполненных дуэтом.

В музыкальной традиции планеты Бемоль для записи высоты звука используются целые числа. В соответствии с этой традицией лучшие композиторы планеты Бемоль составили длинное послание-дуэт, однако в последний момент выяснилось, что положительную реакцию у Диезян вызывают только гармоничные дуэты (гармоничным в понимании Диезян является дуэт, где разница высот исполняемых одновременно звуков не превосходит K).

В связи с этим открытием совет по коммуникациям планеты Бемоль принял решение использовать в качестве послания самый длинный из всех гармоничных фрагментов созданного произведения. Помогите членам совета отыскать этот фрагмент.

Формат входного файла

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

Вторая строка содержит N целых чисел A_N — последовательность звуков первой партии дуэта.

Третья строка содержит N целых чисел B_N — последовательность звуков второй партии дуэта.

Первая и вторая партия исполняются одновременно.

Формат выходного файла

Выходной файл должен содержать две строки: первая — последовательность чисел, составляющих искомый фрагмент первой партии, вторая — соответствующая последовательность из второй партии. Если в партии встречается несколько гармоничных фрагментов одинаковой длины, выведите первый из них. Если подходящего фрагмента не существует, выведите единственное число 0.

Ограничения

1 ≤ N ≤ 10⁴, −1000 ≤ A_N, B_N ≤ 1000, 1 ≤ K ≤ 100

Примеры тестов

10 3
-5 -11 44 2 91 33 14 22 10 8
-7 18 41 2 90 0 16 21 9 50

44 2 91
41 2 90

5 1
1 2 3 4 5
10 20 30 40 50

0