Вы когда-нибудь мечтали стать главным героем компьютерной игры? Главный герой этой истории, Бранимир, мечтает сейчас именно об этом.

Мир в мечте Бранимира состоит из N небоскребов, пронумерованных слева направо. Для i -го небоскреба, известна его высота H _i и количество золотых монет G _i на крыше этого небоскреба. Игра начинается с прыжка на любой из небоскребов и состоит из нескольких ходов. На каждом ходу Бранимир может прыгнуть на любой небоскрёб, находящийся справа от него, но так, чтобы высота нового небоскрёба была не меньше того небоскрёба, на котором сейчас сидит Бранимир. Оказавшись на крыше небоскреба, Бранимир собирает все золотые монеты на ней. Бранимир может закончить игру после любого количества шагов (возможно, нулевого), но он должен собрать не менее K золотых монет, чтобы перейти на следующий уровень.

Бранимир хочет узнать, сколько существует способов сыграть в эту игру так, чтобы перейти на следующий уровень. Две игры называются разными, если существует небоскреб который был посещен в одной игре, но не был посещён в другой.

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, пронумерованных от 1 до N , Мирко имеет номер 1 . У всех кроме Мирко есть начальник. Начальник может иметь несколько подчинённых, но не более одного своего начальника.

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

Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 и так далее. Потом тот, кто на самом деле сделал работу, осознаёт, насколько эта капиталистическая система несправедлива и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации. Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.

Как известно, в июне во Флатландии будет проходить чемпионат Юпитера по футболу. В турнире примут участие n команд, а сам турнир будет разыгран в один круг, в ходе которого каждая команда сыграет с каждой другой командой.

На Юпитере выпускают футбольную форму m цветов. Каждая команда привезёт с собой два комплекта формы различных цветов. Разумеется, во время матча все игроки одной команды должны быть одеты в форму одного цвета, отличного от цвета формы другой команды.

Для судейства всех матчей этого чемпионата был приглашён глава Фантастической Инопланетной Футбольной Ассоциации Йозеф. Перед началом матча Йозеф назначает каждой из команд цвет футболок, в которых игроки выйдут на поле. Разумеется, выбирать можно только из тех двух цветов футболок, которые привезла с собой команда. После этого Йозеф выбирает себе футболку какого-то цвета, отличного от обоих цветов, в которых будут играть команды. Таким образом, обе команды и судья будут находиться на поле в футболках разного цвета. Любую футболку и команды, и Йозеф могут использовать в неограниченном количестве игр чемпионата.

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

Злой Конь объявляет набор в Злую Лигу Зла! Он начертил своим копытом на бумаге длинную строку s , состоящую только из символов « ( », « ) » и « ? » и послал всем потенциальным кандидатам. Желающий подать заявку в злодеи должен для каждого символа « ? » выбрать: заменить его на открывающую скобку или на закрывающую. В Злую Лигу Зла попадёт тот из них, у кого в получившейся строке можно будет выделить самую длинную подпоследовательность , являющуюся правильной скобочной последовательностью.

Подпоследовательностью строки называется строка, получающаяся из данной удалением какого-то (возможно нулевого) количества символов. Например, строки « abc », « ac », « bcc » и « abbcc » являются подпоследовательностями строки « abbcc », а строки « cb » и « ba » не являются. Обратите внимание, пустая строка является подпоследовательностью любой строки.

Последовательность круглых скобок называется правильной в следующих случаях:

1. Если она пустая.
2. Если она состоит из правильной скобочной последовательности, заключённой в скобки.
3. Если она состоит из двух правильных скобочных последовательностей, записанных одна за другой.

Например, последовательности круглых скобок « ()() » и « ((()))() » являются правильными, а « )(() », « ((((( » и « ()) » — нет.

Доктор Хоррибл уже давно мечтает попасть в Злую Лигу Зла, но из-за его пацифизма у него не очень-то хорошо выходит совершать злые поступки. Решает задачи Доктор Хоррибл тоже неважно, поэтому попросил вас помочь ему справиться с головоломкой от Злого Коня.

Дима архитектор. А ещё Дима фотограф. Он часто носится по свету и фотографирует местные Биг Бены и прочие крутые сооружения.

На этот раз Дима приехал в Берляндию, знаменитую своим метрополитеном. Он состоит из n линий, каждая из которых представлена прямой на карте города. На пересечении каждых двух линий метрополитена расположены станции, наземные павильоны которых признаны национальными памятниками архитектуры. Как только Дима увидел их с экрана своего смартфона, он мгновенно загорелся желанием их сфотографировать.

Специально для этой цели он решил воспользоваться маршрутным вертолётом, с которого планирует осуществлять съёмку. Вертолёты компании летают по t маршрутам. Каждый маршрут представляет собой прямую линию. Дима может сделать фотографию, находясь в любой точке маршрута, однако, чем меньше расстояние до станции, тем больше деталей будет видно на снимке, и он соберёт больше лайков в социальных сетях. Вот тут Диме нужна ваша помощь.

Вам даны n прямых, задающих линии метро, и t прямых, задающих доступные вертолётные маршруты. Дима просит для каждого маршрута найти расстояние до ближайшей к нему станции.

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