Задача 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