\textit{You hit the emperor lich with full force and slay it. There is a stair leading upwards here. You climb upstairs. You drink from the pool. You feel much better. The karmic lizard punches through your armor and hits you. You die...} After an epic fight with the emperor lich, the hero struggles to escape the dungeon consisting of \textbf{n} chambers and \textbf{n−1 }corridors connecting them. He starts in chamber number \textbf{1} and must reach chamber number \textbf{t}, moving only along the corridors. All chambers are reachable from chamber number \textbf{1}. Bruised after the last fight, the hero starts the journey with \textbf{0} hit-points (\textbf{HP}). These points represent his health -- if ever they fall below zero, the hero’s story ends there as a tragic one. In some chambers there are monsters -- a monster must be fought, and it always manages to take some of the hero’s \textbf{HP}. In some other chambers there are magic pools -- every pool restores some number of the hit-points. There is no upper limit on the hero’s health. Every chamber can be visited multiple times, but the gain or loss of \textbf{HP} happens only once, on the very first visit. Determine whether the hero can escape the dungeon alive. \InputFile The first line of input contains the number of test cases \textbf{tests}. The descriptions of the test cases follow: The first line of each test case contains two integers: the number of chambers \textbf{n }(\textbf{2 }≤ \textbf{n }≤ \textbf{200000}) and the number of the exit chamber \textbf{t }(\textbf{2 }≤ \textbf{t }≤ \textbf{n}). The second line contains \textbf{n }space separated integers between -\textbf{10^6} and \textbf{10^6} - the \textbf{i}-th of them denotes the \textbf{HP }gain in the \textbf{i}-th chamber (negative denotes a monster, positive -- a pool, and zero means that the chamber is empty). The first chamber does not contain a monster, but a pool is possible there. The exit chamber may contain a pool or a monster, and the monster will have to be fought before escaping. The next \textbf{n−1} lines contain the descriptions of corridors. Each one contains a pair of integers -- the ends of a corridor. \OutputFile For each test case print a single line containing the word escaped if escape is possible, or trapped otherwise.