Qaçış#6770
Siz bütün gücünüzlə Lich İmperatoruna zərbə vurub onu öldürdünüz. Çıxışa aparan bir pilləkən var idi. Siz yuxarı qalxdınız. Hovuzdan su içdiniz. Özünüzü daha yaxşı hiss etdiniz. Karmik kərtənkələ zirehinizdən keçib sizi öldürür. Siz ölürsünüz...
Lich İmperatoru ilə epik döyüşdən sonra qəhrəman n otaqdan və onları birləşdirən n - 1 dəhlizdən ibarət zindandan çıxmalıdır. O, 1 nömrəli otaqdan başlayır və yalnız dəhlizlərdən keçərək t nömrəli otağa çatmalıdır. Bütün otaqlar 1 nömrəli otaqdan əlçatandır. Keçən gecə aldığı zərbədən dolayı qəhrəman hərəkətə 0 xal (HP) ilə başlayır. Bu xallar onun sağlamlıq səviyyəsini göstərir - əgər bu səviyyə sıfırdan aşağı düşərsə, qəhrəmanın hekayəsi faciəvi şəkildə sona çatır.
Bəzi otaqlarda canavarlar var - canavarla döyüşmək lazımdır, buna görə də qəhrəman bu halda həmişə xal (HP) itirəcək. Digər bəzi otaqlarda isə sehrli hovuzlar yerləşir - hər hovuz müəyyən miqdarda həyat xalını bərpa edir. Qəhrəmanın həyatının yuxarı limiti yoxdur. Hər otağı bir neçə dəfə ziyarət etmək olar, lakin HP qazanılması və ya itirilməsi yalnız ilk ziyarət zamanı baş verir.
Qəhrəmanın zindandan sağ çıxıb-çıxa bilməyəcəyini müəyyən edin.
Birinci sətir testlərin sayını tests göstərir. Hər testin strukturu aşağıdakı kimidir:
Birinci sətir iki ədəd ehtiva edir: otaqların sayı n (2 ≤ n ≤ 200000) və çıxış olan otaqların sayı t (2 ≤ t ≤ n). İkinci sətir n tam ədəd ehtiva edir, hər biri -10^6 ilə 10^6 arasında dəyişir, i-ci ədəd i-ci otaqda qazanılan xal (HP) miqdarını göstərir (mənfi ədəd canavarı, müsbət ədəd hovuzu, sıfır isə boş otağı göstərir). Birinci otaqda canavar yoxdur, lakin hovuz ola bilər. Çıxış olan otaqda həm canavar, həm də hovuz ola bilər və çıxmadan əvvəl canavarı mütləq öldürmək lazımdır.
Növbəti n - 1 sətir dəhlizlərin təsvirini verir. Hər biri dəhlizin uclarını göstərən iki tam ədəd ehtiva edir.
Hər test üçün ayrı sətirdə escaped sözü əgər qaçış mümkündürsə və ya trapped əks halda yazın.
Nümunə 1