34942번 - 시우 제국에 내리는 비

문제

국가원수로서, 당신은 시우 제국에 닥칠 폭우를 대비해야 한다. 시우 제국에는 $N$개의 도시가 있으며, $i$번 도시는 제방과 수도시설의 개발 수준에 따른 피해 가중치 $A_i$를 가진다. 모든 도시에는 비가 올 예정이며, 도시별로 강수량을 0ドル$ 이상 1ドル$ 이하 범위의 실수로 표현할 것이다. 유감스럽게도 예보 시스템의 한계로 인하여 각 도시의 정확한 강수량은 알 수 없었다. 따라서, 당신은 강수량이 도시마다 독립적이고 앞서 말한 범위 내에서 균등분포를 따를 것이라고 가정하기로 했다. 도시는 강수량에 피해 가중치를 곱한 만큼의 피해를 입는다. 이를테면 1ドル$번 도시의 강수량과 피해 가중치가 각각 0ドル.5,ドル 3ドル$일 경우, 1ドル$번 도시는 1ドル.5$만큼의 피해를 받게 될 것이다.

당신은 대비책을 세우기에 앞서 각 도시가 $N$개의 도시 중 가장 큰 피해를 받은 도시가 될 확률을 구해두려고 한다. 가령 2ドル$개의 도시가 있어 각각의 피해 가중치가 1ドル,ドル 2ドル$라면, 1ドル$번 도시가 0ドル.25,ドル 2ドル$번 도시는 0ドル.75$가 된다. $N$개의 도시의 피해 가중치가 입력으로 주어질 때, 각 도시가 가장 큰 피해를 받은 도시가 될 확률을 출력하라.

입력

첫 번째 줄에 $N$이 주어진다. (1ドル \le N \le 10^6$)

두 번째 줄에 각 도시의 피해 가중치 $A$의 값이 순서대로 주어진다. (0ドル < A_i < 998,244円,353円$)

입력으로 주어지는 수는 모두 정수이다.

출력

$N$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 도시가 가장 큰 피해를 받은 도시가 될 확률을 998ドル,244円,353円$으로 나눈 나머지를 출력한다. 정확히 말하면, 정답을 적당한 자연수 $x,ドル $y$가 있어 $\frac{x}{y}$로 표현 가능할 때 $x \equiv yz \pmod{998,244円,353円}$를 만족하는 0ドル$ 이상 998ドル,244円,353円$ 미만의 정수 $z$를 출력한다.

제한

노트