Побег
Вы со всей силой ударили императора Лича и убили его. К выходу вела лестница. Вы взобрались наверх. Выпили воды из бассейна. Почувствовали себя лучше. Кармическая ящерица проникает сквозь Ваши доспехи и убивает Вас. Вы умираете...
После эпической схватки с императором Лича, герою надо выбраться из подземелья, состоящего из n комнат и n - 1 коридора, соединяющего их. Он стартует из комнаты 1 и должен достичь комнату t, двигаясь только по коридорам. Все комнаты достижимы из 1. Будучи контуженным прошлой ночью, герой начинает движение с 0 очками (HP). Они показывают уровень его здоровья – если он падает ниже нуля, то история героя трагически заканчивается.
В некоторых комнатах находятся монстры – с монстром следует сражаться, поэтому герой всегда в этом случае потеряет очки (HP). В некоторых других комнатах расположены магические бассейны – каждый бассейн восстанавливает некоторое количество очков жизни. Верхнего лимита жизни героя не существует. Каждую комнату можно посетить несколько раз, но получение или потеря HP случается только раз, в момент первого визита.
Определите, сможет ли герой выбраться из подземелья живым.
Входные данные
Первая строка содержит количество тестов tests. Структура каждого теста следующая:
Первая строка содержит два числа: количество комнат n (2 ≤ n ≤ 200000) и количество комнат, являющимися выходом t (2 ≤ t ≤ n). Вторая строка содержит n целых чисел в промежутке от -10^6 до 10^6, i-ое из которых указывает на количество очков (HP), получаемое в i-ой комнате (отрицательное число означает монстра, положительное - бассейн, ноль означает что комната пуста). Первая комната не содержит монстра, но бассейн может находиться в ней. Комната, являющаяся выходом, может содержать как монстра, так и бассейн, и монстра следует обязательно убить перед выходом.
Следующие n - 1 строк задают описания коридоров. Каждая из них содержит пару целых чисел - концы коридора.
Выходные данные
Для каждого теста вывести в отдельной строке слово escaped если побег возможен или trapped иначе.