Las ~N~ ~(1 \leq N \leq 10 000)~ vacas del Granjero Juan (GJ) convenientemente numeradas desde ~1...N~ están de pie en una línea. Cada vaca tiene una altura entera positiva (que es un poco desconocida). Solo te dicen la altura ~H~ ~(1 \leq H \leq 1 000 000)~ de la vaca más alta junto con el índice ~I~ de esa vaca.

El Granjero Juan ha hecho una lista de ~R~ ~(0 \leq R \leq 10 000)~ líneas de la forma "la vaca ~17~ ve la vaca ~34~". Esto significa que la vaca ~34~ es al menos tan alta como la vaca ~17~, y que todas las vaca entre la ~17~ y ~34~ tiene una altura que es estrictamente más pequeña que la de la vaca ~17~.

Para cada vaca de ~1...N~, determine su altura máxima posible, tal que toda la información proporcionada sigue siendo correcta. Está garantizado que es posible satisfacer todas las restricciones.

Entrada

• Línea 1: Cuatro enteros separados por espacios: ~N~, ~I~, ~H~ y ~R~.

• Líneas 2…R+1: Dos enteros distintos separados por espacios ~A~ y ~B~ ~(1 \leq A, B \leq N)~, lo que indica que la vaca ~A~ puede ver a la vaca ~B~.

Ejemplo de Entrada

9 3 5 5
1 3
5 3
4 3
3 7
9 8

Detalles de la Entrada

Hay 9 vacas, y la tercera es la más alta con una altura de 5.

Salida

• Líneas 1…N: La línea ~i~ contiene la altura máxima posible de la vaca ~i~.

Ejemplo de Salida

5
4
5
3
4
4
5
5
5