34474번 - 매직 리그 서브태스크

문제

매직 리그는 마술사들이 리그 형식으로 마술 쇼를 펼치는 유명한 TV 프로그램이다. 내일은 유명한 마술사, 앨리스와 밥이 대결을 펼치기로 했다.

내일의 대결은 정확히 $R$회 펼쳐진다. 각 대결에서, 앨리스와 밥은 치열한 매직 쇼 승부를 펼치고, 둘 중 승자는 승리의 증표인 코인을 하나 얻는다. 프로그램이 시작하기 전에 두 마술사는 코인을 가지고 있지 않고, 각 대결에서 얻은 코인은 누적된다.

대결의 승자는 $R$회의 대결이 끝나고 둘 중 더 코인을 많이 가진 사람이 된다. 따라서, 대결 도중 두 마술사가 획득한 코인의 개수의 차이를 의미하는 '코인 차'는 둘 중 누가 더 유리한지 가늠할 수 있는 중요한 지표가 된다. 엄밀하게, '코인 차'는 현재 앨리스가 획득한 코인의 수에서 밥이 획득한 코인의 수를 뺀 값이다.

또한, 앨리스와 밥은 비슷한 실력을 가지고 있기 때문에, 첫 번째 대결에서 승리할 확률이 $\frac{p}{360}$로 항상 서로 같다. 어떤 대결에서 아무도 승리하지 못할 수도 있다. (1ドル-\frac{p}{180}$에 해당하는 경우이다.) 둘 모두 승리할 수는 없다. 매 대결 이후에는 앨리스와 밥이 승리할 확률이 각각 $\frac{q}{360}$만큼 높아진다. ($\frac{q}{360}<0$라면 그 절댓값만큼 낮아진다.) 확률이 $\frac{1}{2}$을 초과하면 $\frac{1}{2}$가 되고, 0ドル$ 미만이 되면 0ドル$이 된다.

이 엄청난 프로그램에 흥미를 가지고 있는 캐서린은, 내일의 대결 결과가 너무나 궁금한 나머지, 오늘 안에 각 대결 이후 누가 더 유리해질지 알아내는 사람에게 큰 보상을 주겠다고 약속했다. 정확하게는, $L\leq i\leq R$인 각 $i$에 대해, $i$번째 대결 이후 '코인 차'가 양수일 확률을 구해야 한다.

당신은 이 문제를 해결하고 캐서린에게 큰 보상을 받고자 한다.

입력

첫째 줄에 네 정수 $L,ドル $R,ドル $p,ドル $q$가 공백으로 구분되어 주어진다.

출력

$R-L+1$개의 줄에 걸쳐 각 줄에 하나의 정수를 출력한다.

$i$번째 줄에는 하나의 정수 $A_i$를 출력한다. $L+i-1$번째 대결 이후 '코인 차'가 양수일 확률이 $\frac{r}{s}$일 때, $A_i$는 $A_i\times s=r\bmod{998,244円,353円}$인 가장 작은 음이 아닌 정수이다. 이 확률은 $\frac{r}{s}$ 형태로 나타낼 수 있다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\leq L\leq R\leq 20,000円,000円$
• $R-L\leq 200,000円$
• 0ドル\leq p\leq 180$
• $-180\leq q\leq 180$

서브태스크

힌트