En un valle alpino hay ~N~ pueblos (numerados ~1 ... N~) conectados solo por ~N - 1~ carreteras. Si bien todavía es posible llegar de cualquier aldea a cualquier otra aldea, esto puede llevar bastante tiempo. Esto se vuelve particularmente molesto si tiene que comprar suministros básicos, ya que hay una tienda en sólo S de los N pueblos.

Este invierno la situación empeoró aún más debido a las fuertes nevadas. Por tanto, sería aconsejable para salir del valle, es decir, llegar al único pueblo ~E~ en el puerto de montaña que conecta el valle al mundo exterior, o al menos comprar suficientes suministros para los próximos meses. Escuchaste en la radio esta mañana que la nieve ha inutilizado una de las ~N - 1~ carreteras; sin embargo, no podías entender claramente cuál.

Ahora quiere saber si usted y sus amigos pueden salir del valle y, de no ser así, a qué distancia cada uno de ustedes tiene que conducir al menos para llegar a un pueblo con tienda. Como aún no está seguro de cuál carretera está bloqueada y como tus amigos viven en diferentes pueblos del valle, debes escribir un programa que responde a esta pregunta para ~Q~ consultas dadas las combinaciones de aldea y carretera bloqueada.

Entrada

La primera línea contiene los números enteros ~N, S, Q~ y ~E~, donde ~N~ es el número de aldeas, ~S (1 \le S \le N)~ es el número de tiendas, ~Q~ es el número de consultas a su programa y ~E (1 \le E \le N)~ es el pueblo al que hay que llegar para salir del valle.

Cada una de las siguientes ~N - 1~ líneas consta de tres números enteros ~A~, ~B~ y ~W~. Esto significa que hay una carretera de longitud ~W (1 \le W \le 10^9)~ que conecta los pueblos ~A~ y ~B~ ~(1 \le A \le N, 1 \le B \le N)~.

Luego siguen ~S~ líneas, cada una de las cuales consta de un solo entero ~C~, lo que significa que hay una tienda en el pueblo ~C (1 \le C \le N)~. Tenga en cuenta que todos los enteros de estas líneas son diferentes, es decir, nunca hay más de una tienda en un pueblo.

Por último, hay ~Q~ líneas, cada una de las cuales contiene dos números enteros ~I~ y ~R~, lo que significa que la carretera ~I~ de la entrada (~1 \le I <N~, enumerados en el orden en que aparecen) ya no se puede utilizar y quiere saber si sus amigos en la aldea ~R (1 \le R \le N)~ pueden salir del valle y si no, a qué distancia el pueblo más cercano con tienda es.

Salida

Su salida debe constar de Q líneas. La i-ésima línea debe contener la respuesta a la i-ésima consulta de la entrada. Más precisamente, la línea respectiva debe contener la cadena “escaped” (sin comillas) si es posible salir del valle; si no, debe contener la distancia al pueblo más cercano con una tienda, o la cadena "oo" si ya no hay ninguna tienda accesible.

Puntuación

Subtarea 1. (9 puntos) ~1 \le N \le 100~, ~1 \le Q \le 10 000~, y solo hay una carretera conectando los pueblos ~A~ y ~B~ si ~ | A - B | \leq 1~

Subtarea 2. (27 puntos) ~1 \le N \le 1 000~, ~1 \le Q \le 1 000~.

Subtarea 3. (23 puntos) ~1 \le N \le 100 000~, ~1 \le Q \le 100 000~, y ~S = N~.

Subtarea 4. (41 puntos) ~1 \le N \le 100 000~, ~1 \le Q \le 100 000~.

Ejemplo de entrada 1

5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5

Ejemplo de salida 1

escaped
3
oo

Ejemplo de entrada 2

10 2 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7 
2 1
1 5
8 4
6 2
7 7

Ejemplo de salida 2

8
escaped
escaped
escaped
0