Игра средней оплаты

Игра средней оплаты – это игра для двух игроков, которая ведется на ориентированном графе. Вершины графа разделены на два множества: A и B. Первому игроку принадлежат вершины из множества A, а второму игроку – вершины из множества B. Каждая дуга uv графа помечена некоторым целым числом w_uv.

Игра протекает следующим образом. Исходно специальная фишка помещается в выделенную вершину s графа. Затем игроки делают ходы, перемещая фишку по графу. Если фишка находится в вершине из множества A, то фишку перемещает первый игрок, а если в вершине из множества B, то второй игрок. Игроки поддерживают специальный счетчик z, в котором ведется суммирование чисел, записанных на дугах, по которым перемещается фишка. Исходно z = 0, после того как фишка перемещается по дуге uv, выполняется присваивание z = z + w_uv. Игра продолжается до бесконечности.

Цель первого игрока – добиться, чтобы z → +∞ (иначе говоря, добиться, чтобы для любого числа x с некоторого момента игры z никогда не становился меньше чем x). Цель второго игрока – добиться, чтобы z → −∞. Если ни один из игроков не может добиться успеха, игра считается ничейной.

Например, рассмотрим игру, граф которой изображен на рисунке. Закрашенные вершины принадлежат первом игроку, а незакрашенные – второму. Исходно фишка располагается в вершине s.

Эта игра выигрышная для первого игрока. Он должен переместить фишку в вершину e а, второй игрок может либо перейти в положительный цикл f → g → f , из которого нет выхода, или переместить фишку в вершину c, из которой первый игрок переместит ее в b, и затем опять в e, добавляя +1 к z.

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

Петя собирается поиграть в эту игру с Васей. Петя будет первым игроком, а Вася – вторым. Игроки выбрали граф для игры и стартовую вершину. Теперь Петя считает, что он выиграет в игре и выбрал себе выигрышную стратегию. Но он не до конца уверен. Он просит вас проверить: действительно ли выбранная им стратегия является выигрышной, то есть гарантирует, что z → +∞ вне зависимости от действий Васи.

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа n и m – количество вершин и ребер в графе, соответственно. (1 ≤ n ≤ 2 000, 1 ≤ m ≤ 10 000). Вторая строка содержит n английских букв, которые описывают владельцев вершин, вершины, принадлежащие Пете, помечены как «A», а вершины, принадлежащие Васе – как «B». Третья строка содержит 0_s – номер стартовой вершины.

Следующие m строк описывают дуги графа. Каждая дуга задается вершиной, в которой она начинается, вершиной, в которую она ведет, и числом, которым она помечена. Пометки дуг не превосходят 10⁵ по абсолютной величине. Из каждой вершины исходит хотя бы одна дуга.

Последняя строка описывает стратегию Пети. Она содержит n целых чисел. Для каждой вершины задано либо число 0, если соответствующая вершина принадлежит Васе, либо номер дуги, по которой Петя собирается пойти, если фишка окажется в этой вершине. Дуги нумеруются с 1 в том порядке, в котором они заданы во входном файле.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите «Win», если стратегия Пети действительно является выигрышной. В противном случае следует вывести либо «Lose», если Вася может выиграть, либо «Draw», если Вася выиграть не может, но может свести игру к ничьей. В этих случаях на второй строке выведите Васину выигрышную, либо ничейную стратегию (против заданной Петиной) в том формате, в котором во входном файле задана стратегия Пети.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!