Задача A. Аквалангист ≡

Условие

Аквалангист Джонс находится в море в координате x_j, y_j на глубине h_j метров. Джонс заметил акулу, которая находится в координате x_s, y_s на глубине h_s метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью v_s м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

Формат входных данных

Входные данные содержат в двух строках целые числа x_j, y_j, h_j и x_s, y_s, h_s, v_s.

Формат выходных данных

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |x_j|, |y_j|, h_j, |x_s|, |y_s|, h_s ≤ 10⁵

1 ≤ v_s ≤ 100

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

0 0 1
100 100 100 1

YES

0 0 1
0 0 2 2

NO

Задача B. Быки и коровы 2 ≡

Условие

На одномерном поле длиной N клеток пасутся быки и коровы. Каждая клетка либо пустая, либо занята быком, либо занята коровой.

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

Требуется написать программу, определяющую участок с наибольшим количеством коров. Если таких участков несколько, то нужно выбрать среди них участок с наибольшим количеством быков. Если и таких участков несколько, то нужно выбрать участок наиболее удалённый от краёв поля. Если же и таких участков несколько, то необходимо выбрать самый левый из них.

Формат входных данных

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

Формат выходных данных

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

Ограничения

1 ≤ N < 10⁵, 1 ≤ h ≤ N

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

15 5
XX...XXYYYXX.YY

6 10

Задача C. Жадная последовательность ≡

Условие

Дана последовательность из N целых чисел a_i. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

Требуется написать программу, выводящую последовательность, которая получится после выполнения M операций.

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

Первая строка входного файла содержит целые числа N и M — количество элементов последовательности и количество операций.

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

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

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 10⁵

−10⁴ ≤ a_i ≤ 10⁴

Описание подзадач и системы оценивания

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

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

4 1
1 2 3 4

3 4 3

4 2
3 2 1 1

3 4