As spring arrives and everything comes back to life, with the pandemic gradually fading, Yazid brings his $n$ friends to visit the T University campus. For convenience, we label them from $1$ to $n$.

The layout of the T University campus can be abstracted as an undirected graph with $n$ vertices (labeled $1$ to $n$). For any two distinct vertices $i$ and $j$ ($i \neq j$), there is an undirected edge between them that takes $|i - j|$ units of time to traverse.

Lilacs are one of the signature flowers of T University. As it is currently the season when lilacs are in full bloom, there are $m$ roads on campus that are lined with lilacs. Yazid's friends are very interested in these lilacs, so they all wish to traverse all $m$ roads that have lilacs.

Yazid's friends start from vertex $s$. The $i$-th friend wishes to end their tour at vertex $i$. At the same time, as mentioned above, each friend must pass through each of the $m$ roads with lilacs at least once.

Yazid's friends do not want to be too exhausted, so they wish to spend as little time as possible to achieve their goals. Please calculate the minimum time required for each of Yazid's friends to complete their goal.

Input

The first line contains $3$ non-negative integers $n, m, s$. It is guaranteed that $1 \le s \le n$ and $m \le \frac{n(n-1)}{2}$.

The next $m$ lines each contain $2$ integers $u, v$, describing an undirected edge with lilacs connecting vertices $u$ and $v$. It is guaranteed that $1 \le u, v \le n$ and $u \neq v$, and that each undirected edge is described at most once.

For all lines in the input, multiple integers within a line are separated by a single space.

Output

Output a single line containing $n$ integers separated by single spaces, where the $i$-th integer describes the minimum time required for Yazid's $i$-th friend to complete their goal.

Examples

Input 1

4 3 1
1 2
4 2
3 1

Output 1

6 7 8 7

Note 1

One optimal route for the $1$st friend is to start from $1$, pass through $2, 4, 3$, and finally return to $1$, consuming $|1-2|+|2-4|+|4-3|+|3-1| = 6$ units of time.

One optimal route for the $2$nd friend is to start from $1$, pass through $2, 4, 3, 1$, and finally arrive at $2$, consuming $7$ units of time.

One optimal route for the $3$rd friend is to start from $1$, pass through $2, 4, 1$, and finally arrive at $3$, consuming $8$ units of time.

One optimal route for the $4$th friend is to start from $1$, pass through $3, 1, 2$, and finally arrive at $4$, consuming $7$ units of time.

Input 2

6 0 2

Output 2

1 0 1 2 3 4

Note 2

Since $m = 0$, there are no mandatory roads, so each friend can simply reach their destination directly via a single edge.

Input 3

5 4 1
1 2
3 4
4 5
3 5

Output 3

8 7 6 7 8

Subtasks