Язык программирования

Антон Б., суперспособный ученик 8 класса, обладает неудивительными математическими способностями. Побывав однажды на экскурсии в Колоколамске, он понял, что легко может написать программу, которая бы предсказывала стоимость его любимых конфет на любой промежуток дней вперед. 
Используя эту программу, Антон Б. решил  приобрести на все свои карманные деньги конфеты (а их у него было всего 10 рублей), затем, чуть позже, продать все купленные им конфеты. Таким образом, Антон Б. хочет заработать как можно больше денег на новый ноутбук. 
Так как  Антон Б. еще несовершеннолетний и один ездить в другие города не может, ему нужно понять, в какие из двух дней попросить старшего брата отвезти его в Колоколамск. Старший брат совершеннолетний и очень любит своего младшего брата, поэтому всегда готов ему помочь.
Так как Антон Б. очень торопится на кружок по информатике, он просит вас определить эти два дня в ближайшие N дней. 

Входные данные
В первой строке записано число N (2 <= N <= 100000) количество дней, на которые Антон Б. делает прогноз. Вторая строка содержит N целых положительных чисел ai (1 <= i <= N , 1 <= a_i <=  5000 ), где ai - предсказанная стоимость конфет в i-й день.

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

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

 

Примеры

№	Входные данные	Выходные данные
1	6 10 3 5 3 11 9	2 5
2	4 5 5 5 5	0 0

В городе M расположена кольцевая автодорога длиной в N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы стоимость доставки мусора была минимальной. Стоимость доставки мусора вычисляется, как вместимость пункта сбора умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым. Контейнеры нумеруются с 1 до N.
Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?

Описание входных данных
Даны два входных файла (файл A и файл B), каждый из которых содержит (2 <= N <= 10⁹) чисел. Первое число N - количество контейнеров для мусора. Последующие N чисел - количество килограмм мусора, которое производится на точке.

Описание выходных данных
Одно число - номер контейнера для мусора, рядом с которым стоит расположить перерабатывающий завод.
В ответе укажите два числа в одной строке через пробел: ответ для файла А и ответ для файла В.


Пример организации входных данных:
6
8
20
5
13
7
19
Для данного примера ответ - 6 (7*1 + 13*2 + 5*3 + 20*2 + 8*1 + 19*0).

 

Текстовый файл состоит не более чем из 10⁶ символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Текст разбит на строки различной длины. Назовем подпоследовательность оригинальной, если она ограничена слева подстрокой AВ, а справа подстрокой BA (данные подстроки также входят в подпоследовательность) и при этом в этой подпоследовательности нет других букв А и B. Оригинальная подпоследовательность не может начинаться в одной строке, а заканчиваться в другой.
Определите, сколько  всего  оригинальных подпоследовательностей во всем файле, а также длину максимальной из них.

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

Пример
Исходный файл:
AAABCAABCBAA
ZZABZZZBABCBA
QRABUTUUBA
В этом примере всего 4 оригинальных подпоследовательности (AВСВА, ABZZZBA, ABCBA, ABUTUTBA)
Самая длинная подпоследовательность (ABUTUTBA) имеет длину 8.
Ответ: 48


Файл к заданию

N коров (1 ≤ N ≤ 10⁵) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L₁,R₁)…(L_M,R_M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10⁹) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L_i и R_i, два целых числа в интервале 1…N, где L_i<R_i.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой     [1,2,3,4,5,6,7]  После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4].  Повторив оба шага ещё раз получим результат, приведенный в выводе.

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 10⁵) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

1. Ровно одна корова была инфицирована изначально (нулевой пациент).
2. После того, кaк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
3. Однажды заболев, она остаётся больной.

К несчастью, ФД не знает, какая из его N коров, является "нулевым пациентом", кроме того он не знает значение K!. Помогите ему сузить диапазоны этих неизвестных, основываясь на его данных. Гарантируется, что ответ существует.

Входные данные
Первая строка ввода содержит N (2<= N <=100) и T (1 <= T <= 250). Следующая строка содержит строку длиной N, состоящую из 0 и 1, описывающую текущее состояние N коров ФД, 0 - здорова, 1 - больна. Каждая из последующих T строк описывает запись из списка взаимодействий ФД, и состоит из трёх чисел, t,x,y, где t - положительное целое время взаимодействия (t <= 250), x и y - различные целые в интервале 1…N, указывающее какие коровы взаимодействовали в момент времени T. В один момент времени T происходит не более одного взаимодействия.

Выходные данные
Выведите одну строку, содержащую три целых числа x,y,z, где x - количество различных коров, которые могли быть "нулевым пациентом", y - минимально возможное значение K, подходящее к исходным данным, z - наибольшее возможное значение K, подходящее к исходным данным. Если для K нет верхней границы, выведите "Infinity" для z. Заметим, что возможно K=0.
 

Примеры

№	Входные данные	Выходные данные
1	4 3 1100 7 1 2 5 2 3 6 2 4	1 1 Infinity

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L. 

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке подается 3 числа: количество чисел N (1 <= N <= 1 000 000),  L и C (\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 1):
5 3 1
1
-1
-5
-2
3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной -4 будет: -5+(-2)+3. 
Ответ (для С = 3 и L = 1): -4. 

В ответе укажите два числа в одной строке через пробел: сначала значение искомой суммы для файла А, затем для файла B.

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

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L.

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке подается 3 числа: количество чисел N (1 <= N <= 1 000 000),  L и C (1 <= L, C <= N <= 10⁶). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 3):
5 3 3
1
-1
2
-2
3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3. 
Ответ (для L = 3 и С = 3): 3. 

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

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

Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество нечётных чисел кратно K = 7. Найдите наибольшую сумму такой подпоследовательности. 

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.

Пример организации исходных данных во входном файле (для К=4):
6
8
17
3
13
11
21

В этом наборе можно выбрать последовательности 8+17+3+13+11 (сумма 52) и 3+13+11+21 (сумма 48). 
Ответ (для K = 4): 52. 

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

Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество чётных чисел кратно K = 8. Найдите наибольшую сумму такой подпоследовательности. 

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.

Пример организации исходных данных во входном файле (для К=4):
6
9
16
4
12
10
18

В этом наборе можно выбрать последовательности 9+16+4+12+10 (сумма 51) и 4+12+10+18 (сумма 44). 
Ответ (для K = 4): 51. 

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

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1<= N <= 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:
7
21
13
9
19
17
26
95
В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

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

Ушан с планеты Блук открыл пекарню. В его пекарне продается N видов тортов. Каждый вид торта имеет три параметра: «красота», «вкус» и «популярность». I-й вид торта имеет красоту xi, вкус yi и популярность zi. Эти значения могут быть нулевыми или отрицательными.
Громозека решил, что купит М кусочков торта. Он выбирает набор следующим образом:
- Нельзя использовать два и более куска одного и того же вида торта.
- При указанном выше условии выбирается набор тортов, который максимизирует (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности).
Найдите максимально возможное значение (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности) для набора тортов, который выберет Громозека.

Входные данные
В первой строке через пробел записаны два целых числа N (1<=N<=1000) и M (0<=M<=N). В следующих N строках записано по  три целых числа xi, yi и zi (-10⁹<=xi, yi, zi <=10⁹, 1<=i<=N).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9	56	Подумайте о 2-м, 4-м и 5-м видах тортов. Общая красота, вкус и популярность будут следующими: Красота: 1 + 3 + 9 = 13 Вкус: 5 + 5 + 7 = 17 Популярность: 9 + 8 + 9 = 26 Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 13 + 17 + 26 = 56. Это максимальное значение.
2	5 3 1 -2 3 -4 5 -6 7 -8 -9 -10 11 -12 13 -14 15	54	Подумайте о том, чтобы иметь 1-й, 3-й и 5-й виды тортов. Общая красота, вкус и популярность будут следующими: Красота: 1 + 7 + 13 = 21 Вкус: (−2) + (- 8) + (- 14) = - 24 Популярность: 3 + (- 9) + 15 = 9 Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 21 + 24 + 9 = 54. Это максимальное значение.
3	10 5 10 -80 21 23 8 38 -94 28 11 -26 -2 18 -69 72 79 -26 -86 -54 -72 -50 59 21 65 -32 40 -94 87 -62 18 82	638	Если у нас есть 3-й, 4-й, 5-й, 7-й и 10-й виды тортов, общая красота, вкус и популярность будут -323, 66 и 249 соответственно. Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 323 + 66 + 249 = 638. Это максимальное значение.
4	3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000	30000000000	Значения красоты, вкуса и популярности тортов, а также значение, которое будет напечатано, могут не соответствовать 32-битным целым числам.

 

Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: Y [i₁, i₂, i₃, i₄] = min(X[j₁, j₂, j₃, j₄]), где 1 ≤ i_k ≤ N − M + 1, i_k ≤ j_k ≤ i_k + M − 1, а M -  заданное число.

Входные данные
В первой строке входного файла задаются N и M (1 ≤ M ≤ N). Остальные строки файла содержат элементы массива X. Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению 10⁹. Они расположены в таком порядке, что считать их можно с помощью псевдокода:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]

Выходные данные
Выведите искомый массив Y в том же формате, в котором был дан массив X.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 1	1
2	3 2 3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1	-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5

Выберите неверное утвеждение:

1) Возможно инициализировать нестатические поля данных в статическом конструкторе.
2) Можно инициализировать статические поля данных в нестатическом конструкторе, но после этого они теряют свой статический характер.
3) Можно инициализировать статические поля данных как в статических, так и в нестатических конструкторах, но статические поля данных теряют свой статический характер.
4) Возможно инициализировать нестатические поля данных в нестатическом конструкторе.

Какое из следующих утверждений верно?

A. Конструктор может использоваться для установки значений по умолчанию.
B. C# обеспечивает конструктор копирования.
C. Деструкторы используются как с классами, так и со структурами.
D. Класс может иметь более одного деструктора.

Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

Когда луч приходит в угол, через который проходят зеркальные стены, дальше он идет так, как показано на рисунках (серым цветом показаны клетки, которые окружены зеркальными стенами). Аналогичным образом луч ведет себя, когда приходит на границу лабиринта.


Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).

Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.

Примеры

№	Входные данные	Выходные данные
1	3 5 X.... ..... .....	XXXXX XXXXX XXXXX
2	3 3 ... ..X ...	/X\ X.X \X/

«Нарисуйте» с помощью символов на экране лес. При этом не пользуйтесь командами перемещения курсора по экрану. Ваша программа должна последовательно выводить символы строк (или строки целиком).

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

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

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

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

Гарантируется, что входные данные будут таковы, что количество символов, которое нужно будет вывести в одной строке, не превысит 79.

Выходные данные
Выведите требуемый «рисунок». Для лучшего понимания смотрите примеры.
 

Примеры

№	Входные данные	Выходные данные
1	2 3 2 3 3	...#......#.... ..###....###... ...#....#####.. ..###.....#.... .#####...###... ...#....#####.. ..###..#######. .#####....#.... #######..###... ........#####.. .......#######. ......#########
2	3 1 1 2 1 3 2	#.#...#... ..#..###.. .###..#... .....###.. ....#####. ......#... .....###.. ....#####. ...#######

Егор очень любит Москву и часто ходит на прогулку, чтобы полюбоваться ее видами.

Москва в представлении Егора представляет собой длинное прямое шоссе, вдоль которого расположено n башен, пронумерованных в порядке их следования числами от 1 до n. Все башни имеют различные высоты, которые выражаются целыми числами от 1 до n . Высота башни с номером i составляет h_i .

Однако Егор не любит возрастающие последовательности. Его разочаровывают тройки башен, таких что с возрастанием их индексов их значения тоже возрастают. Более формально, тройка башен с номерами i , j и k разочаровывает Егора, если i < j < k и h_i < h_j < h k .

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

Входные данные
Первая строка входных данных содержит единственное число n — количество башен в Москве ( 1 ≤ n ≤ 8000 ).

Вторая строка входных данных содержит n различных натуральных чисел, i -е из них h i — высота i -й башни ( 1 ≤ h_i ≤ n ).

Выходные данные
Выведите одно число — количество троек башен, которые разочаруют Егора.

Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ».
 

Примеры

№	Входные данные	Выходные данные
1	5 1 3 4 2 5	5
2	3 3 1 2	0

Максим вырос, разочаровался в большой науке и теперь работает авиадиспетчером. Каждый день он делает очень важное и ответственное дело: сажает самолеты.

Этот процесс не такой уж сложный, как может показаться на первый взгляд. В аэропорту, в котором работает Максим, всего одна посадочная полоса, поэтому самолеты должны садиться по очереди. Посадка занимает b минут. Если самолет прилетел, а посадочная полоса занята, его отправляют совершать дополнительные круги над городом до тех пор, пока он не прилетит к аэропорту со свободной взлётно-посадочной полосой. Один круг занимает f минут. Если посадочная полоса свободна, самолёт немедленно начинает посадку. Если несколько самолётов подлетают к аэропорту со свободной посадочной полосой одновременно, то один из них идёт на посадку, а другие отправляются совершать дополнительные круги.

Сегодня в аэропорт должны прилететь n самолетов, известно время прилета каждого из них. За какое время все самолёты совершат посадку?

Входные данные
В первой строке даны три целых числа n, b, f — количество самолетов (1≤n≤1000), время, которое занимает посадка и время, которое занимает один круг над аэропортом (1≤b, f≤10⁹  ). В следующей строке дано n целых чисел t_i — времена прибытия самолетов, перечисленные в произвольном порядке (0≤t_i≤10⁹ ).

Выходные данные
Выведите одно число: время, за которое все самолёты совершат посадку.
 

Примеры

№	Входные данные	Выходные данные
1	10 5 12 13 0 1 10 20 20 2 1 10 20	79

Когда Дядя Фёдор уехал домой в город, следить за хозяйством остались Матроскин и Шарик. Но поскольку Дядю Фёдора очень волновали дела в Простоквашино, они договорились, что каждую неделю Матроскин будет писать письмо с отчетом о делах. Довольно скоро Матроскин понял, что письма идут слишком долго, поэтому решил отправлять телеграммы. Обычно отчеты очень длинные, поэтому Матроскину пришлось отправлять несколько телеграмм. Чтобы Дяде Фёдору было удобнее разобраться в пришедших телеграммах, Матроскин следует следущим правилам:

В каждой телеграмме должно быть не более 140 символов, включая пробелы и знаки препинания.
Исходный текст должен быть разбит на телеграммы по пробелам, при этом пробел, по которому разбивается телеграмма, уничтожается.
Если телеграмма не является последней, в её конец нужно дописать три точки.
Если телеграмма не является первой, в её начало нужно дописать три точки.
Чтобы сэкономить деньги на отправке телеграмм, Матроскин хочет разбить текст на как можно меньшее количество.

Помогите Матроскину разбить исходный текст на как можно меньшее количество телеграмм по приведенным выше правилам.

Входные данные
На вход подается строка из маленьких латинских букв и пробелов. Она не начинается и не заканчивается пробелами и никакие два пробела в ней не идут подряд. Длина строки не превышает 10000.

Выходные данные
В первой строке выведите число N – количество телеграмм, на которое надо разбить исходную строку. В следующих N строках выведите сами телеграммы. Если текст передать заданным способом невозможно, выведите −1.

 

Примеры

№	Входные данные	Выходные данные
1	deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl bwuoio	2 deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl... ...bwuoio