Contest.samsu.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

C. Теплые воспоминания

Задачу добавил: alef

Успешно сдано решений: 13

Ограничение по времени: 3 с

Ограничение  по памяти: 256 Мб

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

Но тут министр времяисчисления Харитон вмешался. Напомнил Фалалею, что, во-первых, неделю назад министр науки был в командировке деловой и на совещании отсутствовал, а, во-вторых, добавил, что он, Харитон, каждый раз записывает, какая была температура в начале совещания. И ни разу не было, было, было, даже однажды случалось — как раз во время командировки Фалалея.

Фалалей тут же ответил, что с месяц назад и вовсе было, хотя, конечно, с не спутать. Словом, споры жаркие начались: кто да что вспомнить может. Но у Харитона всё записано! 

Харитон вёл записи в течение дней. В течение этих дней каждый министр (за исключением самого Харитона) побывал в одной командировке —- иными словами, отсутствовал в дни, начиная с и заканчивая (включительно;  — номер министра). Министр назвал температуру как ту, которая запомнилась ему более всего за эти дней.

Министр времяисчисления Харитон хочет проверить, действительно ли в один из дней, когда министр присутствовал на совещаниях, в большой зале была указанная им температура . При этом, если в точности такой температуры не было, Харитон сообщит, что министр что-то путает, и назовёт температуру, минимально отличающуюся в большую сторону от . Если же министр назвал температуру, большую чем любая из возможных в дни его присутствия на совещаниях, Харитон сообщит, что министр вводит коллег в заблуждение, и назовёт температуру ядра Солнца, которая составляет (примерно) .

Ваша задача — определить для каждого министра, какую температуру назовёт для него Харитон.

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

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

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

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

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

Выведите чисел — ответы Харитона министрам. Разделяйте числа пробелом или переводом строки.

Пример

Входные данные
10 5
1 -3 -6 6 3 4 -9 2 9 3
3 5 -6
8 8 5
4 8 -9
1 7 2
4 8 10
Выходные данные
-3 6 -6 2 15700000 

Сдать задачу

Задать вопрос жюри по этой задаче