Hello World Examples

hello_world.rb

mod =998244353
Matrix_distribution=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
def power(a,b):
    res = 1
    while b >0:
        if b&1:
            res = (res * a)%mod
        a=(a*a)%mod
        b>>=1
    return int(res)

assign_operation_mp ={}
def precompute():
    Matrix_distribution[0][0] = 0
    Matrix_distribution[1][0] = 1
    Matrix_distribution[2][0] = 2
    Matrix_distribution[3][0] = 3
    Matrix_distribution[0][1] = 1
    Matrix_distribution[1][1] = 0
    Matrix_distribution[2][1] = 3
    Matrix_distribution[3][1] = 2
    Matrix_distribution[0][2] = 2
    Matrix_distribution[1][2] = 3
    Matrix_distribution[2][2] = 0
    Matrix_distribution[3][2] = 1
    Matrix_distribution[0][3] = 3
    Matrix_distribution[1][3] = 2
    Matrix_distribution[2][3] = 1
    Matrix_distribution[3][3] = 0

    assign_operation_mp['^']=(Matrix_distribution)
    Matrix_distribution[0][0] = 0
    Matrix_distribution[1][0] = 0
    Matrix_distribution[2][0] = 0
    Matrix_distribution[3][0] = 0
    Matrix_distribution[0][1] = 0
    Matrix_distribution[1][1] = 1
    Matrix_distribution[2][1] = 2
    Matrix_distribution[3][1] = 3
    Matrix_distribution[0][2] = 0
    Matrix_distribution[1][2] = 2
    Matrix_distribution[2][2] = 2
    Matrix_distribution[3][2] = 0
    Matrix_distribution[0][3] = 0
    Matrix_distribution[1][3] = 3
    Matrix_distribution[2][3] = 0
    Matrix_distribution[3][3] = 3
    assign_operation_mp['&'] = (Matrix_distribution)

    Matrix_distribution[0][0] = 0
    Matrix_distribution[1][0] = 1
    Matrix_distribution[2][0] = 2
    Matrix_distribution[3][0] = 3
    Matrix_distribution[0][1] = 1
    Matrix_distribution[1][1] = 1
    Matrix_distribution[2][1] = 1
    Matrix_distribution[3][1] = 1
    Matrix_distribution[0][2] = 2
    Matrix_distribution[1][2] = 1
    Matrix_distribution[2][2] = 2
    Matrix_distribution[3][2] = 1
    Matrix_distribution[0][3] = 3
    Matrix_distribution[1][3] = 1
    Matrix_distribution[2][3] = 1
    Matrix_distribution[3][3] = 3
    assign_operation_mp['|'] = (Matrix_distribution)

def application():
    L =str(input())
    if L=='#':
        print("748683265 748683265 748683265 748683265")
    else:
        postFix = ""
        st = []
        prob_ways =[]
        for i in range(0,len(L)):
            if L[i]==')':
                while st[len(st)-1] != '(':
                    postFix += st[len(st)-1]
                    st.pop()
                st.pop()
            elif L[i]=='(':
                st.append(L[i])
            elif L[i]=='#':
                postFix+=L[i]
            else:
                st.append(L[i])

        for i in postFix:
            if i=='#':
                prob_ways.append([1,1,1,1])
            else:
                a1=prob_ways[len(prob_ways)-1]
                prob_ways.pop()
                a2=prob_ways[len(prob_ways)-1]
                prob_ways.pop()
                Ways=[0,0,0,0]
                for j in range(0,4):
                    for k in range(0,4):
                        idx=int(assign_operation_mp[i][j][k])
                        Ways[idx]=int(int(Ways[idx]+(a1[j]*a2[k])%mod)%mod)
                prob_ways.append(Ways)
        ansWays=prob_ways[len(prob_ways)-1]
        Mod=int((ansWays[0]+ansWays[1]+ansWays[2]+ansWays[3])%mod)
        Mod_Inv=int(power(Mod,mod-2))
        str1=""
        # for i in range(0,4):
        #     str1=str1+str((ansWays[i]*Mod_Inv)%mod)+" "
        str1 = str((ansWays[0]*Mod_Inv)%mod)+" "+str((ansWays[1]*Mod_Inv)%mod)+" "+str((ansWays[2]*Mod_Inv)%mod)+" "+str((ansWays[3]*Mod_Inv)%mod)
        print(str1,"\n")

def main():
    t=int(input())
    precompute()
    while t>0:
        application()
        t=t-1
if __name__=="__main__":
    main()