끝말잇기

흰곰과 흑곰은 토끼에게 $N$개의 단어가 있는 사전을 받았다. 두 곰은 끝말잇기를 즐겨 한다. 끝말잇기는 두 곰이 번갈아가며 사전에 있는 단어를 말하는 놀이이다. 곰은 직전에 상대가 말한 단어의 마지막 글자로 시작하는 단어만 말할 수 있다. 말할 수 있는 단어가 하나 이상 있으면 곰은 그중 하나를 무작위로 고르며, 각 단어가 고には 확률은 모두 같다. 말할 수 있는 단어가 하나도 없으면 끝말잇기를 끝낸다. 마지막으로 단어를 말한 곰이 이긴다.

사전에 있는 한 단어를 여러 번 말할 수 있다. 이 때문에 끝말잇기가 끝나지 않을 수도 있다. 토끼는 곰이 단어를 말할 때마다 끝말잇기가 끝날 수 있는지 판단한다. 두 곰이 이후에 어떤 단어를 말하더라도 끝말잇기가 끝날 수 없다면 토끼가 끝말잇기를 끝낸다. 이때는 토끼가 이긴다.

흰곰이 사전의 $i$번째 단어를 말하며 끝말잇기를 시작할 때, 흰곰이 이길 확률을 $\alpha_i$, 흑곰이 이길 확률을 $\beta_i$, 토끼가 이길 확률을 $\gamma_i$, 끝말잇기가 끝날 때까지 두 곰이 말하는 단어 수의 기댓값을 $\delta_i$라고 정의한다. 흰곰, 흑곰, 토끼는 수학적으로 계산한 $\alpha,\beta,\gamma,\delta$ 값과 직접 끝말잇기를 해서 얻은 $\hat\alpha,\hat\beta,\hat\gamma,\hat\delta$ 값을 비교해 보려 한다. $1$부터 $N$까지의 정수 $i$에 대해 $\alpha_i,\beta_i,\gamma_i,\delta_i$를 구하시오.

첫 번째 줄에 사전에 있는 단어의 개수 $N$이 주어진다. $(1\le N\le 2\times 10^5)$ 두 번째 줄부터 $N$개의 줄에 걸쳐 $i+1$번째 줄에 사전의 $i$번째 단어 $w_i$가 주어진다. $(1\le\lvert w_i\rvert\le 10;$ $i\neq j\implies w_i\neq w_j)$ 모든 단어는 로마자 대문자로 이루어져 있다.

첫 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 $\alpha_i,\beta_i,\gamma_i,\delta_i$를 각각 $998\,244\,353$으로 나눈 나머지를 공백으로 구분하여 출력한다. 엄밀하게는 유리수 $\alpha_i,\beta_i,\gamma_i,\delta_i$ 각각을 $\frac{P}{Q}$로 나타낸다. 여기서 $P\ge 0$, $Q>0$, $\gcd(P,Q)=1$인 정수이다. $0\le R<998\,244\,353$인 정수 $R$을 구하면 $R\times Q\equiv P\pmod{998\,244\,353}$을 만족한다. 이런 $R$은 유일하게 존재함이 보장된다.