Tallest Cow

Farmer John's $N$ cows ($1 \le N \le 10000$), numbered $1$ through $N$, are standing in a line. Every cow has a positive integer height, most of which are secret. You are told only the height $H$ ($1 \le H \le 1000000$) of the tallest cow and its index $I$.

You are also given $R$ pieces of information ($0 \le R \le 10000$) of the form "cow $a$ sees cow $b$". This means cow $b$ is at least as tall as cow $a$, and every cow strictly between $a$ and $b$ is strictly shorter than cow $a$.

For each cow from $1$ to $N$, determine its maximum possible height so that all of the given information still holds. It is guaranteed that all constraints can be satisfied simultaneously.

• Line 1: Four space-separated integers $N$, $I$, $H$, and $R$.
• Lines 2 to $R+1$: Two distinct space-separated integers $A$ and $B$ ($1 \le A, B \le N$), meaning cow $A$ sees cow $B$.

• Print $N$ lines. Line $i$ contains the maximum possible height of cow $i$.