Codeforces Round 210 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

graphs

greedy

shortest paths

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Levko and Game

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLevko loves sports pathfinding competitions in his city very much. In order to boost his performance, Levko spends his spare time practicing. The practice is a game.

The city consists of *n* intersections connected by *m* + *k* directed roads. Two or more roads can connect the same pair of intersections. Besides, there can be roads leading from an intersection to itself.

Levko and Zenyk are playing a game. First Levko stands on intersection *s*_{1}, and Zenyk stands on intersection *s*_{2}. They both want to get to intersection *f*. The person who does it quicker wins. If they get there at the same time, the game ends with a draw. By agreement both players start simultaneously and move with the same speed.

Levko wants to win very much. He knows the lengths of all the roads in the city. Also he knows that he can change the lengths of some roads (there are *k* such roads at all) if he pays the government. So, the government can change the length of the *i*-th road to any integer value in the segment [*l*_{i}, *r*_{i}] (both borders inclusive). Levko wondered if he can reconstruct the roads so as to win the game and whether he can hope for the draw if he cannot win.

You should consider that both players play optimally well. It is guaranteed that we can get from intersections *s*_{1} and *s*_{2} to intersection *f*.

Input

The first line contains three integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 10^{4}, 1 ≤ *k* ≤ 100). The second line contains three integers *s*_{1}, *s*_{2} and *f* (1 ≤ *s*_{1}, *s*_{2}, *f* ≤ *n*).

The next *m* lines contains the descriptions of the roads that cannot be changed by Levko. Each line contains three integers *a*_{i}, *b*_{i} and *c*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*, 1 ≤ *c*_{i} ≤ 10^{9}), representing a road from intersection *a*_{i} to intersection *b*_{i} of length *c*_{i}.

The next *k* lines contains the descriptions of the roads that can be changed by Levko. Each line contains four integers *a*_{i}, *b*_{i}, *l*_{i} and *r*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*, 1 ≤ *l*_{i} ≤ *r*_{i} ≤ 10^{9}), representing a road from intersection *a*_{i} to intersection *b*_{i}, Levko can set the road's length within limits [*l*_{i}, *r*_{i}].

Consider all intersections numbered from 1 to *n*. It is guaranteed that you can get from intersections *s*_{1} and *s*_{2} to intersection *f*.

Output

In the first line print string "WIN" (without the quotes) if Levko can win this game, string "DRAW" (without the quotes) if Levko can end the game with a draw and "LOSE" (without the quotes) if he loses for sure.

If the answer is "WIN" or "DRAW", then print on the second line *k* space-separated integers — the length of the roads Levko sets in the order they occur in the input.

Examples

Input

4 1 3

1 3 4

3 2 2

1 2 1 3

2 4 1 3

3 4 1 3

Output

WIN

1 1 3

Input

4 1 3

1 3 4

3 2 2

1 2 1 3

2 4 1 3

3 4 1 2

Output

DRAW

1 1 2

Input

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

Output

LOSE

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2024 21:49:06 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|