Втеча
Ви з усієї сили вдарили імператора Ліча і вбили його. До виходу вела драбина. Ви піднялися нагору. Випили води з басейну. Відчули себе краще. Кармічна ящірка проникає крізь Ваші обладунки і вбиває Вас. Ви вмираєте...
Після епічної битви з імператором Ліча, герою потрібно вибратися з підземелля, яке складається з 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 в іншому випадку.