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

Совсем недавно на дорогах страны появились \(M\) полицейских постов (они могут быть не на каждой дороге, и их может быть несколько на одной дороге). Все посты разбиты на \(P\) категорий, на одной дороге бывают посты только различных категорий. Полицейские очень любят переписываться с коллегами своей категории, а электронной почты в стране еще не существует, поэтому для передачи писем они используют проезжающих. Проезжая пост категории \(i\) без письма для полицейских этой категории, Владислав обязательно берет на посту письмо. Проезжая через очередной пост категории \(i\), Владислав обязательно отдает это письмо, причем новое письмо на этом посту он не получает. К концу поездки у Владислава не должно остаться ни одного письма.

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

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

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

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

Игра будет состоять в том, что игрок будет управлять автобусом, перемещающимся по городу. В первой версии игры город будет представлять собой прямоугольное поле размера \(N\times M\) клеток, каждая из которых либо занята зданием, либо свободна (т.е. по ней проходит дорога). Автобус игрока может перемещаться лишь по дорогам, но не по зданиям.

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

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

В результате понятно, что автобус игрока может застрять в тупике, откуда ему будет некуда двигаться. Более того, ясно, что есть клетки, куда заезжать нельзя, т.к., заехав туда, в итоге игрок будет вынужден доехать до тупика.

Строго говоря, пусть игрок перемещает автобус бесконечно долго (т.е. в течение бесконечного количества ходов). Тогда несложно видеть, что в некоторых свободных клетках игрок может бывать бесконечно много раз (при условии, что начальная клетка выбрана удачно), а в некоторых — не более одного (и то лишь в начальной части игры).

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

В секретном 240 отделе ИПФ РАН \(N\) сотрудников и \(N\) компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно \(K\) компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно \(K\) сотрудников.

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

Обратите внимание, что значение \(K\) тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что \(K\) будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений \(K\).