D. Тавас Канзаст

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

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

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

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

Тавас Канзаст амьдардаг. Канзаст $m$ ширхэг $2$ чиглэлт замаар холбогдсон, $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хот байдаг. Бид дурын нэг хотоос дурын өөр хот руу дээрхи замаар дамжин аялах боломжтой. Тиймээс нэг хотыг өөртэй нь холбох, эсвэл $2$ хотын хооронд нэгээс олон зам байж болох юм.

Тавас "Дашти" гэх нэгэн тоглоом зохиожээ. Тэр найз охин Нафастайгаа Дашти тоглохыг хүсэв.

Уг тоглоомд тэд Канзасын хот бүрт дурын бүхэл тоон утга оноож өгөв. $i$-р хотын утга $p_{i}$-тэй тэнцүү. Тоглоомын турш Тавас $s$ хотод, Нафас $t$ хотод байв. Тэд ээлжлэн тоглох ба тоглолт Тавасаас эхэлнэ. Тоглогчийн ээлж ирэхэд сөрөг биш $x$ бүхэл тоог сонгох ба тоглогчийн оноо түүний байгаа хотоос $x$-ээс ихгүй (хамгийн богино) зайд байх бүх хотуудын утгын нийлбэрээр нэмэгдэнэ. Хот бүрийн утга ганцхан удаа ашиглагдана. Өөрөөр хэлбэл, тоглогч нэг хотоос эхний удаа оноо авахад хотын утга $0$ болно.

Нэмэлт дүрэм: тоглогч өмнө нь ашиглагдаагүй ядаж нэг хотын оноог авах байдлаар $x$-ыг сонгоно. Хот нь анхнаасаа $0$ утгатай байж болно гэдгийг анхаараарай. Тоглолтын эхэнд $0$ утгатай хотыг ашиглагдаагүй гэж үзнэ. Өөрөөр хэлбэл тоглогч бүр уг нэмэлт дүрмийг биелүүлэхэд ашиглаж болно.

Аль аль нь нүүдэлгүй болсон үед тоглолт дуусна.

Тоглогчийн оноо нь түүний тоглолтын турш цуглуулсан оноонуудын нийлбэр байна. Хамгийн их оноотой тоглогч ялагч болох ба эсвэл хэрэв тоглогчид ижил оноотой бол тэнцээ болно. Тоглогчид хоёул тоглолтыг $0$ онооноос эхлүүлнэ.

Хэрэв Тавас хожвол тэр найз охиныхоо зүрхийг шархлуулна. Харин Нафас хожвол Тавас уйлна. Гэхдээ хэрэв тэдний оноо тэнцвэл тэд хоёул баяртай байх ба Тавас Нафаст цэцэг өгнө.

Тэд тийм ч сэтгэл хөдлөмтгий биш тул оновчтой тоглоно. Таны даалгавар бол Таваст тоглоом дууссаны дараа юу болохыг хэлэх явдал юм.

Оролт

Оролтын эхний мөр нь $n$ ба $m$ ($2≤n≤2000$, $n-1≤m≤10^{5}$) хоёр бүхэл тоог агуулна.

Хоёр дахь мөр нь $s$ ба $t$ ($1≤s, t≤n$, $s≠t$) хоёр бүхэл тоог агуулна.

Дараагийн мөр нь хоосон зайгаар тусгаарлагдсан $p_{1}, p_{2}, ..., p_{n}$ ($|p_{i}|≤10^{9}$) $n$ ширхэг бүхэл тоонуудыг агуулна.

Дараагийн $m$ мөр нь замуудыг агуулна. Мөр тус бүр нь $v, u, w$ гурван бүхэл тоог агуулах ба эдгээр нь $v$ ба $u$ хотуудын хоорондох замын урт $w$ ($1≤u, v≤n$ and $0≤w≤10^{9}$)-г илэрхийлнэ. Зам нь нэг хотыг өөртэй нь холбодог, мөн хоёр хотын хооронд хэд хэдэн зам байх боломжтой.

Гаралт

Хэрэв Тавас хожвол "Break a heart", Нафас хожвол "$Cry$" гэж хэвлээрэй. Харин хэн ч хожихгүй бол (өөрөөр хэлбэл тоглоом тэнцээгээр дуусвал) "Flowers" гэж хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
4 4
1 2
3 2 5 -11
1 4 2
3 4 2
3 1 5
3 2 1
Гаралт
Cry
Оролт
5 4
1 2
2 2 -5 -4 6
1 2 4
2 3 5
2 4 2
4 5 2
Гаралт
Break a heart
Оролт
2 1
1 2
-5 -5
1 2 10
Гаралт
Flowers
Сэтгэгдлүүдийг ачааллаж байна...