러브 레터

번호가 $1$부터 $n$까지 매겨진 용이 $n$마리 있습니다. 용 $i$의 나이는 $a_i$입니다. $a_i$의 값은 모두 서로 다릅니다. 1번 용은 에비리르입니다.

에비리르는 용 $t$에게 보낼 편지가 있습니다. 나이 차이로 생기는 어색함을 피하려고, 에비리르는 편지를 다른 용에게 보낼 수 있습니다(반드시 $t$번 용일 필요는 없습니다). 편지를 받은 용은 또 다른 용에게 편지를 보낼 수 있으며, 이런 과정을 거쳐 결국 편지를 $t$번 용에게 전달하는 것이 목표입니다.

용 $i$가 편지를 가지고 있을 때, 용 $j$에게 $|a_i - a_j|$의 시간으로 편지를 보낼 수 있습니다. 용은 자기 자신에게 $0$의 시간으로 편지를 보낼 수 있습니다. 서로 절친한 용의 쌍이 $k$개 있습니다. 용 $i$와 $j$가 절친하면, 용 $i$가 $j$에게 편지를 보내는 데 $0$의 시간이 걸리며, 그 반대도 마찬가지입니다.

각 용 $t$($1 \le t \le n$)에 대해 독립적으로 답하세요. 1번 용이 $t$번 용에게 편지를 보내는 데 필요한 최소 총 시간은 얼마인가요?

절댓값 $|x|$는 $x$와 0 사이의 거리입니다. 예를 들어 $|9| = 9$, $|-6| = 6$, $|0| = 0$입니다.

첫 줄에 용의 수 $n$과 절친한 쌍의 수 $k$가 주어집니다($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 2 \cdot 10^5$). 둘째 줄에는 서로 다른 $n$개의 정수 $a_1, a_2, \ldots, a_n$($1 \le a_i \le 10^9$)이 공백으로 구분되어 주어집니다. 이어서 $k$개의 줄에 정수 $u$와 $v$($1 \le u, v \le n$, $u \ne v$)가 주어지며, 이는 용 $u$와 $v$가 절친하다는 뜻입니다. 같은 쌍은 순서와 무관하게 두 번 나오지 않습니다.

공백으로 구분하여 정수 $d_1, d_2, \ldots, d_n$을 출력하세요. 여기서 $d_i$는 1번 용이 $i$번 용에게 편지를 보내는 데 필요한 최소 총 시간입니다.

첫 번째 예제에서 1번 용은 자기 자신에게 $0$의 시간으로 도달합니다. 1번 용과 3번 용은 절친하므로 3번 용도 $0$의 시간으로 도달합니다. 2번 용은 3번 용이 2번 용에게 $|23 - 30| = 7$의 시간으로 보내서 도달하므로 총 $7$입니다. 8번 용은 1번 용이 직접 $|50 - 47| = 3$의 시간으로 보내므로 $3$입니다. 4번 용은 $1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4$로 $7$의 시간이 걸립니다. 5번 용은 $1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4 \xrightarrow{7} 5$로 $14$의 시간이 걸립니다. 6번 용은 $1 \xrightarrow{0} 3 \xrightarrow{0} 7 \xrightarrow{2} 6$으로 $2$의 시간이 걸립니다. 7번 용은 $1 \xrightarrow{0} 7$로 $0$의 시간이 걸립니다.