Левко очень любит соревнования по спортивному ориентированию в своем городе. Чтобы лучше выступать на соревнованиях Левко тренируется все свободное время. Тренировки проводятся в игровой форме.
Город состоит из n перекрестков, которые соединены m + k односторонними дорогами. Между двумя перекрестками может существовать больше одной дороги, а также могут быть дороги из одного перекрестка в него же.
Левко и Зенык играют в игру. В самом начале игры Левко стоит на перекрестке s1, а Зенык — на перекрестке s2. Они оба хотят добраться до перекрестка f. Кто сделает это быстрее, тот и победит. Если они доберутся туда одновременно, то объявляется ничья. По предварительной договоренности игроки стартуют одновременно, а также двигаются по дорогам с одинаковой скоростью.
Левко очень хочет победить в игре. Он знает длины всех дорог в городе и знает, что есть ровно k дорог, длины которых можно изменить, заплатив городскому правительству. По заказу Левко правительство может изменить длину i-ой из этих k дорог на любое целое значение из интервала [li, ri] (оба конца отрезка включаются). Левко стало интересно, может ли он перестроить дороги так, чтобы победить в игре, и если нет, то может ли он надеяться на ничью.
Считайте, что оба игрока действуют оптимально, играя в игру. Гарантируется, что из перекрестков s1 и s2 можно добраться до перекрестка f.
Выходные данные
В первой строке выведите строку «WIN» (без кавычек) — если Левко может победить в этой игре, «DRAW» (без кавычек) — если Левко может достичь ничьи и «LOSE» (без кавычек), если он точно проиграет.
Если ответ «WIN» или «DRAW» во второй строке выведите k целых чисел через пробел — длины дорог, которые устанавливает Левко. Длины для дорог выводите в порядке следования дорог во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1 3
1 3 4
3 2 2
1 2 1 3
2 4 1 3
3 4 1 3
|
WIN
1 1 3
|
|
2
|
4 1 3
1 3 4
3 2 2
1 2 1 3
2 4 1 3
3 4 1 2
|
DRAW
1 1 2
|
|
3
|
5 4 2
1 2 5
1 3 3
1 4 4
2 3 2
2 4 3
3 5 1 5
4 5 4 7
|
LOSE
|