던전 탈출

당신은 리치 황제에게 온 힘을 실은 일격을 날려 쓰러뜨렸다. 위로 올라가는 계단이 있다. 계단을 오른다. 웅덩이의 물을 마신다. 몸이 훨씬 나아졌다. 업보의 도마뱀이 갑옷을 뚫고 당신을 때린다. 당신은 죽었다...

리치 황제와의 장대한 싸움을 끝낸 용사는 이제 던전에서 빠져나가야 한다. 던전은 방 $n$개와 방을 잇는 통로 $n - 1$개로 이루어져 있다. 용사는 $1$번 방에서 출발해 통로만 따라 움직여 $t$번 방까지 가야 한다. $1$번 방에서 모든 방으로 갈 수 있다. 마지막 싸움으로 만신창이가 된 용사는 체력(HP) $0$으로 여정을 시작한다. HP는 용사의 생명이고, 음수로 떨어지는 순간 용사의 이야기는 비극으로 끝난다.

어떤 방에는 몬스터가 있다. 몬스터는 반드시 싸워야 하며, 싸우면 언제나 용사의 HP가 얼마간 줄어든다. 또 어떤 방에는 마법 웅덩이가 있고, 웅덩이는 HP를 얼마간 회복시킨다. 용사의 HP에는 상한이 없다. 같은 방을 몇 번이든 지나갈 수 있지만, 그 방에서 HP가 변하는 것은 처음 들어갈 때 한 번뿐이다.

용사가 살아서 던전을 빠져나갈 수 있는지 판별하시오.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 방의 수 $n$ ($2 \le n \le 200\,000$)과 출구 방의 번호 $t$ ($2 \le t \le n$)가 주어진다. 둘째 줄에는 $-10^6$ 이상 $10^6$ 이하의 정수 $n$개가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 방에서 변하는 HP이며, 음수면 몬스터, 양수면 웅덩이, $0$이면 빈 방이다. $1$번 방에는 몬스터가 없지만 웅덩이는 있을 수 있다. 출구 방에는 웅덩이나 몬스터가 있을 수 있고, 몬스터가 있으면 탈출하기 전에 반드시 싸워야 한다.

다음 $n - 1$개 줄에는 통로의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 그 통로가 잇는 두 방의 번호가 주어진다.

각 테스트 케이스마다 한 줄에, 탈출할 수 있으면 escaped를, 그렇지 못하면 trapped를 출력한다.