Зал Большого галактического театра состоит из \(S\) рядов, по \(S\) мест в каждом ряду.Продажа билетов на каждый спектакль происходит по следующему принципу: первые \(S^2 - N\) ценителей прекрасного приобретают билеты на любые места по их вкусу, а оставшиеся \(N\) кресел администрация бесплатно выделяет студентам, отдавая дань сложившимся традициям.
Во избежание обвинений в дискриминации по половому признаку, рассаживать студентов по этим \(N\) местам необходимо таким образом, чтобы:
Каждое место в зале определяется двумя числами от 1 до \(S\) - номером ряда и номером самого места в этом ряду. Студенческое кресло номер \(i\) расположено в \(a_i\)-м ряду и имеет в нём номер \(b_i\). Поскольку ценители прекрасного могли занять совершенно любые места, числа \(a_i\) и \(b_i\) могут принимать любые значения от 1 до \(S\). В частности, может оказаться так, что в каком-нибудь ряду не будет ни одного студенческого места.
Ради упрощения работы билетёров администрация обращается к вам с заданием написать программу, которая автоматизирует процесс распределения студенческих мест на мужские и женские.
Сначала вводятся два целых числа \(S\) и \(N\) (\(1 \le S \le 100\,000\), \(1 \le N \le \min\{100\,000, S^2\}\)). Далее расположены \(N\) пар натуральных чисел \((a_i, b_i)\), не превосходящих \(S\). Гарантируется, что все места различные.
Если искомого способа не существует, выведите Impossible.Иначе выведите единственную строку из \(N\) символов ‘M’ (мужское) и ‘W’ (женское). Символ на \(i\)-й позиции соответствует статусу \(i\)-го места в той же нумерации, в которой они были перечислены во входных данных.
Тесты состоят из четырёх групп.
2 2 2 1 1 2
MW
3 5 1 2 2 3 1 3 2 1 1 1
WMWWM
В государстве Древоландия есть \(N\) крупных городов, соединенных \(N - 1\) двухсторонними дорогами, причем из любого города можно добраться по этим дорогам до любого другого города. Экономика страны находится в зачаточном состоянии, а Владислав - один из первых бизнесменов в этой стране. В данный момент он подумывает о том, чтобы перевозить крупные партии товаров из одного города в другой.
Совсем недавно на дорогах страны появились \(M\) полицейских постов (они могут быть не на каждой дороге, и их может быть несколько на одной дороге). Все посты разбиты на \(P\) категорий, на одной дороге бывают посты только различных категорий. Полицейские очень любят переписываться с коллегами своей категории, а электронной почты в стране еще не существует, поэтому для передачи писем они используют проезжающих. Проезжая пост категории \(i\) без письма для полицейских этой категории, Владислав обязательно берет на посту письмо. Проезжая через очередной пост категории \(i\), Владислав обязательно отдает это письмо, причем новое письмо на этом посту он не получает. К концу поездки у Владислава не должно остаться ни одного письма.
Кроме того на дорогах страны попадаются разбойники и странники. Каждому разбойнику придется отдать одну монету, чтобы откупиться от него, а каждый странник заплатит одну монету за подвоз вдоль дороги на некоторое расстояние (но число странников на дороге от этого не меняется).
Для любой дороги Владислав знает, сколько разбойников и странников находится на ней в первый год его предпринимательства, и сколько новых будут появляться каждый год (это фиксированные числа, свои для каждой дороги). Владиславу также известно расположение всех полицейских постов и категория каждого их них. Заниматься бизнесом он планирует в течение \(K\) лет.
Помогите Владиславу для каждого года выбрать такой маршрут, чтобы он, перевезя груз из начала в конец, передал все врученные ему по пути письма и при этом получил максимальную прибыль (прибылью называется разница между деньгами, полученными от странников, и отданными разбойникам, в убыточные годы "прибыль" будет отрицательной). Каждый маршрут должен соединять два различных города, и в целях экономии времени не должен проходить по одной дороге дважды. От года к году маршрут может меняться (при этом маршрут в следующем году не обязан начинаться в том городе, в котором закончился маршрут в предыдущем году).
В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(K\). В следующей \((N - 1)\) строке идут описания каждой из дорог. Дорога сначала описывается четырьмя целыми числами \(S_i\), \(F_i\) - номера городов, которые эта дорога соединяет (\(1 \le S_i \le N\), \(1 \le F_i \le N\)), \(A_i\) - число странников на этой дороге в первый год, \(B_i\) - число разбойников на этой дороге в первый год, \(C_i\), \(D_i\) - ежегодные прирост числа странников и числа разбойников соответственно. Затем идет число \(E_i\) - количество постов на этой дороге, а после него \(E_i\) различных натуральных чисел, не превосходящих 20, обозначающих категории постов. Все числа целые и неотрицательные.
Гарантируется, что общее количество всех постов равно \(M\), а также что в течение этих \(K\) лет количество как странников, так и разбойников на каждой дороге не превзойдет \(10\,000\).
Выведите \(K\) чисел - максимальную прибыль, которую можно получить в каждый из \(K\) годов (в том числе отрицательную для убыточных годов). В случае, если в какой-то из годов нет ни одного маршрута, на котором Владислав мог бы передать все врученные ему письма, выведите "Sadness!" (без кавычек).
Тесты состоят из четырех групп.
2 2 2 2 1 7 1 6 10 2 1 2
Sadness! Sadness!
5 5 10 3 2 2 4 8 4 0 4 1 3 10 8 7 2 2 1 4 5 6 8 8 10 2 1 2 1 3 2 5 6 1 1 1
-2 2 6 10 14 18 22 26 30 34
14 14 2 1 3 48 28 23 0 1 1 4 5 25 20 25 7 1 4 3 2 23 16 100 50 1 4 11 9 179 2 57 54 1 2 13 7 30 4 27 23 1 2 10 1 23 6 63 70 2 4 1 3 8 17 7 10 5 0 12 13 34 17 43 67 1 4 4 3 10 4 1 6 1 2 6 1 23 11 38 38 2 2 4 9 8 50 13 0 0 1 1 8 13 43 15 18 19 1 2 10 14 14 40 50 1 1 2
67 111