C. Теплые воспоминания
Задачу добавил: alef
Успешно сдано решений: 13
Ограничение по памяти: 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