你重重地击中了巫妖皇帝并将其击杀。这里有一道向上的楼梯。你爬上楼梯。你喝了池水。你感觉好多了。业力蜥蜴击穿了你的盔甲并击中了你。你死了……

在与巫妖皇帝进行了一场史诗般的战斗后，英雄努力逃离由 $n$ 个房间和连接它们的 $n-1$ 条走廊组成的地下城。他从 1 号房间出发，必须到达 $t$ 号房间，且只能沿着走廊移动。所有房间都可以从 1 号房间到达。在最后一场战斗后，英雄带着 0 点生命值 (HP) 开始了旅程。这些点代表他的健康状况——如果生命值降至零以下，英雄的故事就会以悲剧告终。

有些房间里有怪物——必须与怪物战斗，它总是会扣除英雄的一些 HP。另一些房间里有魔法池——每个池子会恢复一定数量的生命值。英雄的生命值没有上限。每个房间都可以多次访问，但 HP 的增减只会在第一次访问时发生。

请确定英雄是否能活着逃离地下城。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例的第一行包含两个整数：房间数量 $n$ ($2 \le n \le 200\,000$) 和出口房间编号 $t$ ($2 \le t \le n$)。第二行包含 $n$ 个用空格分隔的整数，数值在 $-10^6$ 到 $10^6$ 之间——其中第 $i$ 个数表示在第 $i$ 个房间获得的 HP（负数表示怪物，正数表示池子，零表示该房间为空）。第一个房间没有怪物，但可能有池子。出口房间可能包含池子或怪物，且必须在逃离前与怪物战斗。

接下来的 $n-1$ 行包含走廊的描述。每一行包含一对整数，表示走廊的两端。

输出格式

对于每个测试用例，如果可以逃离，则打印一行包含单词 escaped，否则打印 trapped。

样例

样例输入 1

2
7 7
0 -3 2 2 3 -4 0
1 2
2 3
2 4
1 5
5 6
6 7
3 2
3 3 -4
1 3
2 3

样例输出 1

escaped
trapped