В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с \(N\) вершинами. Сам Петя находится в точке с координатами (\(x\), \(y\)).

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

Петя может перемещаться по плоскости со скоростью \(v\). Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).

Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.

Между \(N\) населенными пунктами совершаются пассажирские рейсы на машинах времени.

В момент времени 0 вы находитесь в пункте \(A\). Вам дано расписание рейсов. Требуется оказаться в пункте B как можно раньше (то есть в наименьший возможный момент времени).

При этом разрешается делать пересадки с одного рейса на другой. Если вы прибываете в некоторый пункт в момент времени \(T\), то вы можете уехать из него любым рейсом, который отправляется из этого пункта в момент времени \(T\) или позднее (но не раньше).

Государство Флатландия представляет собой прямоугольник размером \(M\) × \(N\), состоящий из единичных квадратиков. Флатландия разделена на K провинций (2 <= \(K\) <= 100). Каждая провинция представляет собой связное множество квадратиков, т.е. из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).

Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, которой принадлежит символ \(A\) (заглавная латинская буква \(A\)). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.

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

Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой - второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.

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

У Пети в саду растет яблоня. Воодушевленный историей об Исааке Ньютоне, который, как известно, открыл закон всемирного тяготения после того, как ему на голову упало яблоко, Петя с целью повысить свою успеваемость по физике часто сидит под яблоней.

Однако, поскольку по физике у Пети твердая тройка, яблоки с его яблони падают следующим образом. В какой-то момент одно из яблок отрывается от ветки, на которой оно висит, и начинает падать строго вниз. Если в некоторый момент оно задевает другое яблоко, то то тоже отрывается от своей ветки и начинает падать вниз, при этом первое яблоко не меняет направление своего падения. Вообще, если любое падающее яблоко заденет другое яблоко на своем пути, то оно также начнет падать.

Таким образом, в любой момент каждое яблоко либо висит на ветке, либо падает строго вниз, причем все яблоки кроме первого, чтобы начать падать, должны сначала соприкоснуться с каким-либо другим падающим яблоком.

Выясните, какие яблоки упадут с Петиной яблони.

Город Мехико расположен в прекрасной долине, известной как Долина Мехико, на месте которой много лет назад было озеро. Около 1300 года ацтекские религиозные лидеры выпустили указ о том, что центр озера должен быть засыпан, чтобы построить столицу их империи. В настоящее время озеро полностью осушено.

Вокруг озера до появления ацтеков были расположены c прибрежных городов. Некоторые из этих городов заключили между собой коммерческие соглашения. Между городами, установившими коммерческие соглашения, по озеру на лодках перевозились различные товары. Любую пару городов можно было соединить отрезком прямой, полностью проходящим через озеро.

В какой-то момент короли городов решили упорядочить товароперевозки. Они разработали маршрут товароперевозок, который соединяет все города вокруг озера. Маршрут удовлетворяет следующим условиям:

*Он начинается в каком-либо городе, проходит через каждый прибрежный город и заканчивается в городе, отличном от того, в котором он начался.
*Маршрут проходит через каждый город ровно один раз.
*Любые два последовательно посещаемых города маршрута обязаны иметь между собой коммерческое соглашение.
*Маршрут состоит из отрезков прямых, каждый из которых соединяет два последовательно посещаемых города маршрута.
*Чтобы избежать столкновения лодок, маршрут не должен иметь самопересечений.

На рисунке показано озеро и города вокруг него. Тонкие и жирные линии отрезков обозначают коммерческие соглашения между городами. Жирные линии показывают маршрут грузоперевозок, начинающийся в городе 2 и заканчивающийся в городе 5.

Этот маршрут нигде не имеет самопересечений. Но если построить маршрут, идущий из города 2 в город 6, затем в город 5, а затем в город 1, то он будет неправильным, поскольку имеет самопересечения.

Города нумеруются целыми числами от 1 до \(c\) по направлению часовой стрелки.