가장 키가 큰 소

농부 존의 소 $N$마리($1 \le N \le 10000$)가 $1$번부터 $N$번까지 번호를 달고 한 줄로 서 있습니다. 각 소의 키는 양의 정수이지만 대부분은 비밀입니다. 알려진 것은 가장 키가 큰 소의 키 $H$($1 \le H \le 1000000$)와 그 소의 번호 $I$뿐입니다.

또한 "$a$번 소가 $b$번 소를 본다" 형태의 정보가 $R$개($0 \le R \le 10000$) 주어집니다. 이는 $b$번 소의 키가 $a$번 소보다 크거나 같고, $a$번과 $b$번 사이에 있는 모든 소의 키가 $a$번 소보다 엄밀히 작다는 뜻입니다.

주어진 모든 정보가 그대로 성립하도록 할 때, $1$번부터 $N$번까지 각 소가 가질 수 있는 최대 키를 구하세요. 모든 조건을 동시에 만족시키는 경우가 항상 존재함이 보장됩니다.

• 첫째 줄: 공백으로 구분된 네 정수 $N$, $I$, $H$, $R$.
• 둘째 줄부터 $R$개의 줄: 공백으로 구분된 서로 다른 두 정수 $A$와 $B$($1 \le A, B \le N$). $A$번 소가 $B$번 소를 본다는 뜻입니다.

• $N$개의 줄을 출력합니다. $i$번째 줄에는 $i$번 소가 가질 수 있는 최대 키를 출력합니다.