import fileinput
from operator import itemgetter
def D(a):print(a)
def S(s,I):return int(s.split(" ")[I])
class graph:
    def _cnv(self, H):
        R = 0
        for i in range(self.N):
            R |= H[i]<<(2*i)
        return R

    def __init__(self, N, S, R):
        self.MQ = 10**6+N
        self.BSC = 2**(2*N)
        self.MSK = self.BSC - 1
        self.MX = self.MSK | self.BSC
        self.INF = 2**60
        self.N = N
        self.S = S
        self.R = R
        self.g = [0]*N
        self.G  = [0]*self.MX
        for i in range(N):
            self.g[i] = [0]*N
        for i in range(self.MX):
            self.G[i]=[]
        self.mp = [0]*self.MQ
        self.C = [0]*self.MX
        self.T = 0
        self.D = None
        self.n = N

    def consolidate(self):
        for i in range(self.N):
            self.mp[i] = self._cnv(self.g[i])
            self.C[self.mp[i]] += 1
            for j in range(self.N):
                if self.g[i][j] and self.C[self.mp[i]] == 1:
                    self.G[self.mp[i]].append((self._cnv(self.g[j]), self.g[i][j]))
        self.G[self.mp[0] | self.BSC] = list(self.G[self.mp[0]])
        self.G[self.mp[0]] = []
        self.C[self.mp[0]] -= 1
        self.mp[0] |= self.BSC
        self.C[self.mp[0]] += 1
        for i in range(self.n):
            self.G[self.mp[i]] = list(set(self.G[self.mp[i]]))
        self.dj()

    def dj(self):
        self.D = [-1]*self.MX
        s = [(self.mp[0],0)]
        r = []
        I = 0
        J = 0
        self.T=0
        while I < len(s) or J < len(r):
            if I < len(s) and J < len(r):
                if s[I][1] < r[J][1]:
                    a = s[I][0]
                    p = s[I][1]
                    I += 1
                else:
                    a = r[J][0]
                    p = r[J][1]
                    J += 1
            elif I < len(s):
                a = s[I][0]
                p = s[I][1]
                I += 1
            else:
                a = r[J][0]
                p = r[J][1]
                J += 1
            if self.D[a] != -1 or not self.C[a]:
                continue
            self.D[a] =  p
            self.T += p * self.C[a]
            for b,d in self.G[a]:
                d = self.S if d==1 else self.R
                if self.D[b] == -1 and self.C[b]:
                    if d == self.S:
                        s.append((b,d+p))
                    else:
                        r.append((b,d+p))

    def _add(self,a,b,v,m=True):
        if b != self.mp[0] | self.BSC:
            self.G[a].append((b,v))
        if a != self.mp[0] | self.BSC:
            self.G[b].append((a,v))
        if not m:return
        if a | self.BSC == self.mp[0]:
            self._add(a|self.BSC,b,v,False)
        if b | self.BSC == self.mp[0]:
            self._add(a,b|self.BSC,v,False)

    def add(self,a,b):
        A = self.mp[a]
        B = self.mp[b]
        w = 0
        for i in range(self.N):
            u = (A >> (2*i))&3
            v = (B >> (2*i))&3
            w |= ((u-v+666)%3) << (2*i)
        self.C[w] += 1
        self.mp[self.n] = w
        self.n += 1
        if self.C[w] > 1:
            if self.D[w] != -1:
                self.T += self.D[w]
        else:
            P = []
            if(A | self.BSC == self.mp[0]):
                A |= self.BSC
            if(B | self.BSC == self.mp[0]):
                B|=self.BSC
            self.G[A].sort()
            self.G[B].sort()
            I = 0
            J = 0
            if w | self.BSC == self.mp[0]:
                self.G[w] = list(self.G[self.mp[0]])
                I = 99999999
                J = I
            while I < len(self.G[A]) and J < len(self.G[B]):
                if self.G[A][I][0] < self.G[B][J][0]:
                    P.append((w,self.G[A][I][0],self.G[A][I][1]))
                    I+=1
                elif self.G[A][I][0] > self.G[B][J][0]:
                    P.append((w,self.G[B][J][0],3-self.G[B][J][1]))
                    J+=1
                else:
                    if self.G[A][I][1] != self.G[B][J][1]:
                        P.append((w,self.G[B][J][0],(self.G[A][I][1] - self.G[B][J][1]+666)%3))
                    J+=1
                    I+=1
            while I < len(self.G[A]):
                P.append((w,self.G[A][I][0],self.G[A][I][1]))
                I+=1
            while J < len(self.G[B]):
                P.append((w,self.G[B][J][0],3-self.G[B][J][1]))
                J+=1
            for x,y,z in P:
                self._add(x,y,z)
            self.dj()
        return self.T


z=0
for l in fileinput.input():
    if not z:
        G = graph(S(l,0),S(l,3), S(l,4))
        E = S(l,1)
        Q = S(l,1)
    elif z <= E:
        a = S(l,0)
        b = S(l,1)
        c = l.split(" ")[2][0]
        c = 1 if c == "O" else 2
        G.g[a][b] = c
        G.g[b][a] = c
        if z == E:
            G.consolidate()
    else:
        a = S(l,0)
        b = S(l,1)
        print(G.add(a,b))
    z+=1