Фирма "Макрохард" изобрела новое устройство с целью облегчить труд людей, кому по долгу службы приходится чертить много чертежей, а также школьников, изучающих черчение. Это устройство представляет собой крошечного робота, который умеет ползать по клетчатому листу бумаги. При этом в начале он обязательно должен быть расположен на пересечении линий сетки.
Этот робот умеет выполнять программу, которая может состоять из команд E,W,N,S — переместиться по листу в соседнюю вершину сетки вправо, влево, вперед, назад соответственно. Перемещаясь в соседний узел сетки, робот оставляет за собой ровную линию. При этом по правилам техники безопасности ему категорически запрещается проводить дважды одну и ту же линию, так как при попытке провести линию второй раз, он очень сильно пачкается в своих же собственных чернилах (они очень долго сохнут), и выходит из строя.
При этом, правда, через одну и ту же вершину сетки робот может проходить дважды. Возможно два случая (более толстой линией показано, как мы проезжаем через вершину в первый раз, более тонкой - во второй).
В первом случае мы оба раза проезжаем через вершину "прямо" (будем называть это самопересечением маршрута), а во втором случае — оба раза "поворачиваем" (это будем называть самокасанием).
Разработчики также установили, что в случае самопересечения маршрута робот пачкается в своих чернилах сильнее, чем в случае самокасания, и, если самопересечения встречаются часто, быстро выходит из строя. Поэтому они решили написать для него внутренний оптимизатор программы.
Вам дается программа для робота. Требуется изменить ее так, чтобы узор, получающийся в конце ее работы, был таким же, но при этом при работе робота не возникало самопересечений маршрута.
В первой строке входного файла содержится программа для робота. Таким образом, в первой строке входного файла могут встречаться только символы E,W,N,S, а также пробельные символы, которые должны игнорироваться. Общая длина строки (включая пробельные символы) не превышает 200 символов.
В выходной файл вы должны вывести одну строку с оптимизированной программой. Эта строка должна удовлетворять тем же условиям, что и входная строка.
EENWSSWNN
ENESWSWNN
Сегодня на уроке физики рассказывали удивительные вещи. Придя домой, Витя решил проверить слова учителя о том, что если взять два одинаковых сосуда, соединенных тонкой трубкой на уровне основания, то уровень жидкости при любом ее количестве также будет одинаковым для обоих сосудов.
Способ убедиться в правильности утверждения Витя избрал довольно оригинальный. Он взял аквариум с основанием длиной N и шириной 1, очень высокими стенками, и поставил N –1 перегородку параллельно узкой боковой стенке аквариума, тем самым, разделив аквариум на N одинаковых отсеков. Каждая перегородка имеет ширину 1 и очень большую высоту. Толщиной перегородки можно пренебречь. В каждой из перегородок есть точечное отверстие на высоте Hi, диаметром которого также можно пренебречь. После всех этих приготовлений Витя медленно наливает в первый отсек (между стенкой и 1ой перегородкой) C литров воды. В часть аквариума размером 1x1x1 вмещается ровно один литр воды. Так как стенки и перегородки в аквариуме были очень высокими, то через край вода не переливалась. После установления стационарного состояния он замерил уровень жидкости в каждом из N сосудов.
Теперь он хочет убедиться, что его экспериментальные данные не опровергают законы, рассказанные на уроке. Он обратился к вам с просьбой выяснить, какой должна быть высота жидкости в каждом из сосудов с теоретической точки зрения.
Рассмотрим подробно случай N = 3. Пусть сначала H1 < H2. Как только жидкость в первом отсеке достигнет уровня первого отверстия, вода станет поступать во второй отсек до тех пор, пока уровни в обоих отсеках не сравняются (или уровень воды в первом отсеке окажется равным H1, тогда во втором отсеке он будет на уровне С – H1). Далее уровень жидкости в первых двух частях будет увеличиваться равномерно (или не будет меняться). Как только вода достигнет второго отверстия, вся она будет поступать в третий отсек, опять же до тех пор, пока уровни жидкости во всех трех частях не сравняются или вода в первых двух отсеках достигнет уровня H2. После этого, если воды оказалось достаточно, весь аквариум будет заполняться равномерно.
Пусть теперь H1 > H2. Как только жидкость в первом отсеке достигнет уровня первого отверстия, вся вода станет поступать во второй отсек. Если после этого уровень во втором отсеке сравняется с уровнем второго отверстия, то вода станет выливаться в третий до тех пор, пока высоты жидкостей во втором и третьем отсеках не станут равными. Далее уровень воды в них будет равномерно увеличиваться, пока не достигнет первого отверстия. После этого весь аквариум будет заполняться равномерно.
В первой строке записаны целые N и C (1 ≤ N ≤ 100000, 0 ≤ C ≤ 2*109). В следующих N –1 строках содержится по одному целому числу Hi (0 ≤ Hi ≤ 2*109), обозначающему высоту отверстия в i-й перегородке.
Выведите N чисел, каждое на новой строке, с точностью до шести знаков после десятичной точки —уровень жидкости в 1, 2, ..., N отсеке соответственно.
Частичные ограничения
Первая группа состоит из тестов, в которых N ≤ 100. Оценивается в 30 баллов.
Вторая группа состоит из тестов, в которых N ≤ 10000. Оценивается в 30 баллов.
4 4 3 2 1
3.00000000000000000000 1.00000000000000000000 0.00000000000000000000 0.00000000000000000000
4 10 1 2 3
3.00000000000000000000 3.00000000000000000000 3.00000000000000000000 0.99999999999999911000
Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0, 0), на оси ОХ вплотную друг за другом (вправо). Требуется найти M - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.
Формат входных данных
В первой строке задано число N (1 ≤ N ≤ 8000). Далее идет N строк. В каждой строке содержится два числа: ширина и высота i-го прямоугольника. Значение 
, 0 < hi ≤ 3*104.
Формат выходных данных
Вывести одно число М. Значение M не превосходит 2*109.
3 4 3 2 1 2 5
12
3 4 3 2 1 3 5
15
Дано N чисел. Для каждых K подряд идущих чисел найти минимальное среди них.
Формат входных данных
В первой строке даны числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N), разделенные пробелом. Во второй строке записано N целых чисел через пробел. Числа находятся в диапазоне от -32768 до 32767.
Формат выходных данных
Для каждых К подряд идущих чисел вывести минимальное из них.
Пример
| Входные данные | Выходные данные |
| 11 3 8 764 1 3 85 2 4 5 77 1 5 | 1 1 1 2 2 2 4 1 1 |
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).
Вводится число \(N\) — количество вагонов в поезде (1≤N≤2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до \(N\), каждое из которых встречается ровно один раз.
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:
1) если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число \(K\) (\(K\)≥1),
2) если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число \(K\) (\(K\)≥1).
Если возможно несколько последовательностей действий, приводящих к нужному результату, выведите любую из них.
Если выстроить вагоны по порядку невозможно, выведите одно число 0.
3 3 2 1
YES
4 4 1 3 2
YES
3 2 3 1
NO