В городе S планируется провести чемпионат по новому и очень модному виду спорта — катанию на роликовых коньках по траве. Конечно, одной из важнейших задач при подготовке является выбор символа чемпионата.
Мэр города S решил подойти к вопросу выбора символа очень серьёзно. Он объявил конкурс, на который было подано n вариантов символа. Специальная комиссия разработала m критериев, и каждому из вариантов по каждому критерию была выставлена оценка по десятибалльной шкале.
Затем для каждого варианта была посчитана сумма оценок по всем критериям. Предполагалось, что будет выбран вариант с наибольшей суммой. Однако мэру понравился другой вариант...
Тогда один из заместителей мэра предложил поступить следующим образом: выбрать один из критериев и для всех вариантов заменить выставленные по этому критерию оценки на «противоположные»: если стояла оценка z, то она должна быть заменена на 10 - z.
Другой заместитель мэра предложил объявить один из критериев несущественным и не учитывать в сумме оценки по этому критерию.
Специальная комиссия согласилась реализовать не более одного из этих предложений. Ваша задача — определить, можно ли таким образом добиться, чтобы вариант, который нравится мэру, получал наибольшую суммарную оценку среди всех имеющихся вариантов.
Заметим, что если не только вариант мэра, но и какие-либо другие варианты получат наибольшую суммарную оценку, мэра это устроит: он найдёт способ объяснить, почему предпочтение было отдано понравившемуся ему варианту.
В первой строке содержатся целые числа n и m (2 ≤ n ≤ 20, 2 ≤ m ≤ 20) — количество вариантов символов и количество критериев, по которым выставляется оценка.
Во второй строке содержится целое число k (1 ≤ k ≤ n) — номер варианта символа, который понравился мэру.
Далее следуют n строк, содержащих оценки вариантов по каждому из критериев. Таким образом, в строке #i содержится m целых чисел cij (1 ≤ cij ≤ 10, j = 1, 2, ..., m).
Выведите строку – описание действия и (через пробел) число:
- DEL p — если нужно объявить несущественным критерий #p;
- REV p — если нужно заменить на «противоположные» оценки по критерию #p;
- NOP 0 — если ни замена оценок, ни объявление какого-либо критерия несущественным не приведут к желаемому результату;
- YES 0 — вариант мэра без каких-либо хитростей получает наибольшую суммарную оценку.
Если существует несколько вариантов ответа, выведите любой.
3 2
2
5 8
4 4
4 2
NOP 0
3 2
2
5 8
5 4
4 2
DEL 2
3 2
2
5 6
2 4
4 2
REV 1
3 2
2
5 6
7 4
4 2
YES 0
Обратите внимание, что в четвёртом примере правильными ответами также будут DEL 2 и REV 2.
Ещё один важный вопрос, который предстоит решить устроителям чемпионата — где разместить стадион.
Город S на карте выглядит как прямоугольник, левый нижний угол которого расположен в точке с координатами (0, 0), а правый верхний — в точке с координатами (a, b).
Мэр города S полагает, что если разместить стадион в некоторой точке с координатами (x, y), это приведёт к развитию территории в квадрате с центром в этой точке и стороной 2·d. Стороны этого квадрата будут параллельны сторонам прямоугольника, описывающего город.
Мэру предложили n проектов размещения стадиона.
С точки зрения мэра городская территория достаточно развита, так что он заинтересован в том, чтобы развитие получила как можно большая по площади территория, не относящаяся к городу. При этом он хочет, чтобы развиваемая территория имела хотя бы одну общую точку с городом.
Ваша задача — определить, какой проект следует выбрать мэру. Гарантируется, что среди предложенных проектов существует хотя бы один подходящий.
В первой строке содержатся целые числа a, b, n, d (1 ≤ a, b ≤ 105, 1 ≤ n ≤ 105, 1 ≤ d ≤ 105) — координаты правого верхнего угла города, количество проектов размещения стадиона, половина длины стороны квадрата, территория в котором получает развитие.
Далее следуют n строк. В строке #i содержится пара чисел xi, yi ( - 3·105 ≤ xi, yi ≤ 3·105) через пробел — координаты точки, в которой проект #i предлагает разместить стадион.
В первой строке выведите два целых числа через пробел: номер проекта, который следует выбрать мэру, и площадь территории, которая получит развитие.
Если существует несколько вариантов ответа, выведите любой из них.
10 12 4 3
4 11
7 5
6 -2
5 1
3 30
10 12 4 3
2 14
13 15
-2 -4
13 -2
4 36
Поясним приведённые примеры.
Номера квадратов на рисунках соответствуют номерам их центров в тестовых примерах.
Первому примеру соответствует рис. 1.
Рис.1 Как можно видеть, квадрат под номером #2 полностью находится внутри прямоугольника, очерчивающего город, и охваченная им площадь не получит развития (с точки зрения мэра). Квадраты #1 и #4 позволят развить территории площадью 12 единиц каждая. А вот квадрат #3 даст возможность развить территорию площадью 30 единиц, и именно его номер и эту площадь следует вывести в качестве ответа.
Второй пример проиллюстрирован рисунком 2.
Рис.2 И квадрат #2, и квадрат #4 имеют общие точки с прямоугольником, очерчивающим город. При этом они позволяют развить территорию максимально возможной площади 36 единиц, так что любой из них может быть выбран в качестве правильного ответа (т.е. в примере корректен не только вывод 4 36, но и 2 36). А вот вывод 3 36 будет неправильным: квадрат #3 не имеет ни одной общей точки с городом.
Организаторы чемпионата решили, что добираться до стадиона болельщики будут на трамвае. Для этого существующий трамвайный маршрут, состоящий из n остановок, продлили и дополнили ещё одной остановкой «Стадион».
Однако выяснилось, что поездка на трамвае занимает немало времени. Мэру города S пришла в голову отличная идея: сократить количество трамвайных остановок. Проведя некоторые подсчёты, он решил оставить ровно две остановки: новую — «Стадион» и одну из имеющихся n остановок.
По заданию мэра специалисты по транспорту провели исследование и выяснили, что в настоящее время трамвайным маршрутом пользуется m человек. Для каждого из этих m человек известно, на какой остановке sj он садится в трамвай и на какой остановке fj выходит из трамвая.
Когда из имеющихся n остановок останется одна, пассажиру, который пожелает воспользоваться трамваем, придётся пешком дойти от остановки, где он обычно садился в трамвай, до оставшейся остановки, доехать до остановки «Стадион», а затем дойти от остановки «Стадион» до остановки, где он обычно выходил.
Конечно, пассажир может переквалифицироваться в пешехода и просто дойти пешком от остановки, где он обычно садился, до остановки, где он обычно выходил, т.е. проделать путь длиной в fj - sj остановок.
Мэр полагает, что если путь длиной в fj - sj остановок окажется меньше, нежели пешеходная часть пути с использованием трамвая, пассажир совершенно точно пойдёт пешком.
Мэр ещё не решил, какую из имеющихся остановок он хочет оставить. У него есть список вариантов, и для каждого из них он хотел бы знать, какое количество пассажиров воспользуется трамваем. Ваша задача — определить это количество для каждого номера остановки из списка мэра.
В первой строке содержатся целые числа n, m, q (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 1 ≤ q ≤ 3·105) — количество остановок в маршруте, количество пассажиров, пользующихся маршрутом и количество запросов.
Во второй строке содержится m целых чисел s1, s2, ..., sm (1 ≤ sj ≤ n - 1, j = 1, 2, ..., m), где sj — номер остановки, на которой пассажир #j обычно садится в трамвай.
В третьей строке содержится m целых чисел f1, f2, ..., fm (2 ≤ fj ≤ n, j = 1, 2, ..., m), где fj — номер остановки, на которой пассажир #j обычно выходит из трамвая. Гарантируется, что sj < fj для всех j.
В четвёртой строке содержится q целых чисел r1, r2, ..., rq (1 ≤ rk ≤ n, k = 1, 2, ..., q), где rk — номер оставшейся остановки, для которой нужно вычислить количество пассажиров, воспользовавшихся трамваем.
Выведите q чисел p1, p2, ..., pk.
Число pk (1 ≤ k ≤ q) — это количество пассажиров, которые воспользуются трамваем, если единственной оставшейся из имеющихся остановок будет остановка #rk.
При выводе разделяйте числа пробелами или переводами строк.
5 14 4
2 1 3 3 4 2 1 2 2 1 3 3 4 2
4 3 4 5 5 3 3 5 4 3 5 4 5 4
2 4 3 2
6 5 3 6
Мэр города S полагает, что радикальное сокращение количества остановок популярного трамвайного маршрута вызовет серьёзное недовольство горожан. Поэтому он решил уменьшать количество остановок постепенно.
В настоящий момент маршрут состоит из n остановок, последовательно занумерованных числами от 1 до n. Мэр полагает, что на первом этапе не стоит убирать более двух остановок подряд. По техническим причинам убрать первую и последнюю остановки пока нельзя.
По мнению мэра, любому пассажиру, чтобы сесть в трамвай, придётся пройти не более одной остановки пешком (либо «назад», либо «вперёд»).
Для каждой остановки известно количество пассажиров, садящихся в трамвай. На последней остановке в трамвай никто не садится.
Мэр хочет, чтобы суммарное расстояние, измеренное в количестве остановок, пройденных пассажирами перед посадкой, было максимально возможным. Ваша задача — вычислить, каким будет это суммарное расстояние, а также определить, какие остановки должны остаться в маршруте.
В первой строке содержится целое число n (5 ≤ n ≤ 3·105) — исходное количество остановок в маршруте.
Во второй строке содержится n - 1 целое число p1, p2, ..., pn - 1 (1 ≤ pj ≤ 106, j = 1, 2, ..., n - 1), где pj — количество пассажиров, садящихся в трамвай на остановке #j.
В первой строке выведите два целых числа m и q — максимально возможное суммарное расстояние, измеренное в количестве остановок, пройденных пассажирами перед посадкой, и количество остановок, которые останутся в маршруте.
Во второй строке выведите q целых чисел — номера остановок, которые останутся в маршруте. Выводите номера в порядке увеличения.
10
5 3 8 2 4 9 2 5 1
30 4
1 4 7 10
10
2 7 5 6 4 3 3 2 1
22 5
1 3 6 9 10
Поясним приведённые примеры.
В первом примере в маршруте будет оставлено 4 остановки: #1, #4, #7 и #10. Пассажиры, которые привыкли садиться на других остановках, будут вынуждены пойти на одну из оставшихся.
По мнению мэра, пассажиры, которые обычно садятся на остановке #2, отправятся на остановку #1. Всего таких пассажиров 3, поэтому суммарно они пройдут расстояние в 3 остановки.
Пассажиры, которые обычно садятся на остановке #3, пойдут на остановку #4. Таких пассажиров 8, они пройдут расстояние в 8 остановок, и суммарное расстояние станет равным 11.
На остановку #4 придут и 4 пассажира с ликвидированной остановки #5, увеличив суммарное расстояние ещё на 4 остановки (оно станет равным 15).
Каждый из 9 пассажиров с остановки #6 пройдёт расстояние в одну остановку до остановки #7, и теперь суммарное расстояние составит 24 остановки. Также на остановку #7 придут 5 пассажиров с остановки #8, что прибавит к ответу 5 (итого 29).
Наконец, единственному пассажиру с остановки #9 потребуется идти до остановки #10, что увеличит ответ ещё на единицу.
Таким образом, суммарное расстояние, измеренное в пройденных остановках (быть может, уместно называть это человеко-остановками), окажется равным 30.
Во втором примере существует несколько правильных ответов.
Как легко видеть, из маршрута будут удалены остановки #2, #4, #5, #7 и #8. Это значит, что каждый из пассажиров, привыкших садиться на этих остановках, будет вынужден проделать путь длиной в одну остановку. Поэтому пройденное ими суммарное расстояние будет равно общему количеству пассажиров на этих остановках, т.е. 7 + 6 + 4 + 3 + 2 = 22.
Маршрут, в котором останется 4 остановки, а именно #1, #4, #7 и #10, также будет приводить к суммарному расстоянию в 22 остановки.