Сейчас во всем мире в целях повышения безопасности вождения и уменьшения пробок вводится одностороннее движение. Правительство Берляндии решило не отставать от новой тенденции. Раньше в Берляндии все n городов были соединены n двусторонними дорогами в кольцо, т. е. каждый город был соединен напрямую ровно с двумя другими, и из каждого города можно было добраться до любого другого. Правительство Берляндии ввело одностороннее движение на всех n дорогах, но вскоре выяснилось, что из некоторых городов нельзя доехать до некоторых других. Сейчас для каждой дороги известно, в какую сторону направлено движение по ней, и стоимость перенаправления движения. Какую наименьшую сумму денег придется потратить правительству на переориентирование дорог так, чтобы из каждого города можно было добраться до любого другого?
В первой строке записано целое число n (3 ≤ n ≤ 100) — количество городов (и дорог) в Берляндии. Далее в n строках находятся описания дорог. Каждая дорога описывается тремя целыми числами ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — дорога направлена из города ai в город bi, перенаправление движения стоит ci.
Выведите одно целое число — какую наименьшую сумму денег придется потратить правительству на перенаправление дорог так, чтобы из каждого города можно было добраться до любого другого по этим дорогам.
3
1 3 1
1 2 1
3 2 1
1
3
1 3 1
1 2 5
3 2 1
2
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
39
4
1 2 9
2 3 8
3 4 7
4 1 5
0
Чемпионат Формула-1 состоит из серии гонок, называемых Гран-при. После каждой гонки первым 10 гонщикам начисляются призовые очки в соответствие с занятым местом: 25, 18, 15, 12, 10, 8, 6, 4, 2, 1. По завершении чемпионата гонщик с наибольшим количеством очков объявляется чемпионом. Если таких несколько, чемпионом объявляется тот из них, у кого больше побед (т. е. первых мест). Если таких все еще несколько, выбирается тот из них, у кого больше вторых мест, и так далее, пока есть места, по которым можно сравнивать.
В прошлом году была предложена, но отклонена другая система подсчета очков. По ней чемпион — тот, у кого больше побед. Если таких несколько, то чемпион — тот из них, у кого больше призовых очков. Если таких все еще несколько, то дальнейшее сравнение происходит так же, как и в исходной системе подсчета очков, т. е. сравнивается количество вторых, третьих, четвертых мест и так далее.
Вам даны результаты всех Гран-при сезона. Ваша задача — определить чемпионов по обеим системам подсчета очков. Гарантируется, что в обеих системах чемпион определяется однозначно.
В первой строке записано целое число t (1 ≤ t ≤ 20) — количество гонок (Гран-при). Далее следуют описания всех гонок. Описание каждой гонки начинается с целого числа n (1 ≤ n ≤ 50) на отдельной строчке — количество гонщиков, участвовавших в данной гонке. В следующих n строках заданы результаты гонки, каждая строка содержит имя гонщика. Имена гонщиков даны в порядке от первого до последнего места. Имена состоят из строчных и заглавных латинских букв и имеют длину не более 50 символов. При сравнении имен большие и маленькие буквы следует различать.
Выведите ровно две строки. В первой должно быть записано имя чемпиона по исходной системе подсчета очков, а во второй — имя чемпиона по предложенной системе.
3
3
Hamilton
Vettel
Webber
2
Webber
Vettel
2
Hamilton
Vettel
Vettel
Hamilton
2
7
Prost
Surtees
Nakajima
Schumacher
Button
DeLaRosa
Buemi
8
Alonso
Prost
NinoFarina
JimClark
DeLaRosa
Nakajima
Patrese
Surtees
Prost
Prost
Не гарантируется, что каждый гонщик участвовал в каждой гонке. В чемпионате учитываются все гонщики, участвовавшие хотя бы в одной гонке. Суммарное число гонщиков, участвовавших в чемпионате, не превосходит 50.
Даны точки на плоскости с целыми координатами: M0, A0, A1, ..., An - 1, где n — нечетное число. Определим бесконечную последовательность точек Mi следующим образом: Mi симметрична Mi - 1 относительно 
(для любого натурального числа i). Точка B симметрична A относительно M, если M — центр отрезка AB. Для заданного j найдите точку Mj.
В первой строке записано нечетное целое число n (1 ≤ n ≤ 105), и целое число j (1 ≤ j ≤ 1018) — индекс требуемой точки последовательности. В следующей строке через пробел записаны два целых числа — координаты точки M0. Далее следуют n строк, в i-ой строке через пробел записаны координаты точки Ai - 1. Все координаты не превосходят по модулю 1000.
Выведите через пробел координаты точки Mj.
3 4
0 0
1 1
2 3
-5 3
14 0
3 1
5 5
1000 1000
-1000 1000
3 100
1995 1995
Вы получили в подарок очень умного робота, передвигающегося по прямоугольному полю. К сожалению, робот оказался сломан: он ведет себя как-то странно и передвигается случайным образом. Поле состоит из N строк и M столбцов. Изначально робот находится в клетке на пересечении i-ой строки и j-ого столбца. Далее на каждом шаге робот может пойти на другую клетку. Его цель — попасть на самую нижнюю (N-ую) строку. На каждом шаге робот может остаться на своей текущей клетке, перейти влево, вправо, или вниз на соседнюю клетку. Если робот находится в самом левом столбце, он не может пойти влево, а если он находится в самом правом столбце, он не может пойти вправо. На каждом шаге все возможные действия равновероятны. Найдите математическое ожидание числа шагов, требующихся чтобы дойти до самой нижней строки.
В первой строке через пробел записаны два целых числа N и M (1 ≤ N, M ≤ 1000). Во второй строке через пробел записаны еще два целых числа i и j (1 ≤ i ≤ N, 1 ≤ j ≤ M) — номер строки и столбца, на пересечении которых изначально стоит робот. Клетка (1, 1) — левый верхний угол поля, а (N, M) — правый нижний угол.
Выведите математическое ожидание необходимого числа шагов как минимум с 4 знаками после десятичной точки.
10 10
10 4
0.0000000000
10 14
5 14
18.0038068653
Недавно в Берляндии завершилось строительство Берляндского коллайдера. Коллайдер представляет собой длинный узкий туннель, в котором находятся n частиц. Свяжем с коллайдером одномерную систему координат, идущую слева направо. Для каждой частицы известны ее координата и скорость на момент запуска коллайдера. Скорости частиц после запуска коллайдера не меняются. Берляндские ученые предполагают, что большой взрыв произойдет при первом столкновении частиц, скорости которых направлены в разные стороны. Помогите им определить, сколько времени пройдет после запуска коллайдера прежде чем случится большой взрыв.
В первой строке записано целое число n (1 ≤ n ≤ 5· 105) — количество частиц в коллайдере. Далее в n строках даны описания частиц. Каждая частица описывается двумя целыми числами xi, vi ( - 109 ≤ xi, vi ≤ 109, vi ≠ 0) — координатой и скоростью соответственно. Все координаты различны. Частицы перечислены в порядке возрастания координат. Все координаты даны в метрах, а все скорости — в метрах в секунду. Отрицательная скорость означает, что при запуске коллайдера частица полетит влево, а положительная — что частица полетит вправо.
Если большого взрыва не будет, выведите -1. Иначе выведите одно число — через сколько секунд после запуска коллайдера произойдет большой взрыв. Ваш ответ должен иметь относительную или абсолютную погрешность меньше чем 10 - 9.
3
-5 9
0 1
5 -1
1.00000000000000000000
6
1 3
2 3
3 3
4 -3
5 -1
6 -100
0.02912621359223301065