E. Левко ба тоглоом

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Левко түүний хотод болдог зам олох тэмцээнд туйлын дуртай. Гүйцэтгэлээ сайжруулахын тулд тэрээр хомсон цагаа бэлтгэл хийхэд зарцуулдаг. Бэлтгэл нь тоглоом юм.

Хот нь $m+k$ ширхэг чиглэлт замуудаар холбогдсон зангилаануудаас тогтдог. Олон зам нэг ширхэг зангилааны хосыг хооронд нь холбож байж болно. Мөн зангилааг өөрөө өөртэй нь холбогдог зам ч байж болно.

Левко, Зеник 2 тоглоом тоглож байгаа.Эхлээд Левко $s_1$ зангилаан дээр байгаа ба Зеник $s_2$ зангилаан дээр байгаа. Тэд хэн хэн нь $f$ зангилаан дээр очихыг хүсч байгаа.Хэн хурдан хүссэндээ хүрсэн нь хожно. Хэрвээ нэгэн зэрэг $f$ дээр очвол тэнцсэн тооцно. Тохирсон ёсоор тэд нэгэн зэрэг эхэлж тэнцүү хурдтайгаар хөдөлнө.

Левко хурдан ялахыг хүсч байгаа. Тэр хот доторх бүх замын уртыг мэддэг. Мөн хэрвээ тэр засгийн газарт мөнгийг нь төлбөл тэр зарим замын уртыг өөрчилж чадахаа ч мэдэж байгаа (ихдээ $k$ ширхэг л ийм зам байгаа.). Засгийн газар $i$ дэх замын уртыг $[l_i, r_i] $ завсарт орших дурын тоогоор сольж болно. (захын утгууд орно) Левко замуудыг өөрчилж ялж чадах эсэхээ мэдэхийг хүсчээ мөн хэрвээ ялж чадахгүй бол ядахнаа тэнцэж чадах эсэхээ ч мэдэхийг хүсчээ. .

2 тоглогч боломжит хамгийн сайн хувилбараар тоглох ба $ s1$, $s2$ зангилаануудаас $f$ рүү хүрэх боломжтой.

Оролт

Эхний мөрөнд $n, m ,k (1\le n,m\le 104, 1\le k\le 100)$ тоонууд өгөгдөх ба 2 дахь мөрөнд $s1, s2 , f (1\le s_1,s_2,f\le n)$.

Дараагийн $m$ мөрөнд Левкогийн өөрчилж чадахгүй замууд ба тэдгээрийн мэдээлэл өгөгдөнө. Мөр бүрд $a_i, b_i c_i (1\le a_i,b_i\le n, 1\le c_i\le 10^9)$тоонууд байх ба энэ нь тухайн зам $a_i, b_i$ хотуудыг холбох бөгөөд $c_i$ урттайг илтгэнэ.

Дараагийн $k$ ширхэг мөрөнд Левкогийн өөрчилж чадах замуудын мэдээллүүд өгөгдөнө.Мөр бүр $a_i, b_i, l_i r_i (1\le a_i,b_i\le n,1\le l_i\le r_i\le 10^9)$ энэ нь тухайн зам $a_i, b_i$ хотуудыг холбох бөгөөд Левко энэ замын уртыг $ [l_i,r_i] завсрын дурын бүхэл тоогоор өөрчилж болохыг илтгэнэ$.

Зангилаанууд $1$-с $n$ хүртэл дугаарлагдсан гэж үзнэ. $ s1$, $s2$ зангилаануудаас $f$ рүү хүрэх боломжтой.

Гаралт

Хэрвээ Левко ялж чадах бол эхний мөрөнд "WIN" (хашилтгүйгээр), хэрэв ялж чадахгүй ч тэнцэх боломжтой бол "DRAW" (хашилтгүйгээр), яагаад ч ялж чадахааргүй бол "LOSE" (хашилтгүйгээр) хэвлэ.

Хэрэв хариулт "WIN" or "DRAW" бол дараагийн мөрөнд Левко өөрчилж чадах $k$ ширхэг замуудынхаа уртыг хэд болгосныг оролтод өгөгдсөн дарааллаар нь хэвлэ. ($k$ ширхэг бүхэл тоо хэвлэнэ.)

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
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 
Оролт
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 
Оролт
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
Сэтгэгдлүүдийг ачааллаж байна...