도시

강을 따라 $n$개의 도시가 늘어서 있습니다. 인접한 두 도시 사이에는 도로가 하나씩 놓여 있지만, 모든 도로가 양방향인 것은 아니어서 어떤 도시에서 다른 모든 도시로 갈 수 있는 것은 아닙니다.

어떤 도로들이 놓여 있는지 주어질 때, 각 도시에서 출발하여 도달할 수 있는 다른 도시의 개수를 구하세요.

첫째 줄에 도시의 수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

둘째 줄에는 $n - 1$개의 정수 $d_1, d_2, \dots, d_{n-1}$ ($0 \le d_i \le 2$)이 주어집니다. $d_i$는 $i$번째 도시와 $(i+1)$번째 도시 사이의 도로를 나타냅니다.

• $d_i = 0$이면 $i$번째 도시에서 $(i+1)$번째 도시로 가는 일방통행 도로입니다.
• $d_i = 1$이면 $(i+1)$번째 도시에서 $i$번째 도시로 가는 일방통행 도로입니다.
• $d_i = 2$이면 두 도시를 잇는 양방향 도로입니다.

한 줄에 $n$개의 정수 $w_1, w_2, \dots, w_n$을 공백으로 구분하여 출력합니다. $w_i$는 $i$번째 도시에서 출발하여 도달할 수 있는 도시의 개수이며, 자기 자신은 세지 않습니다.