import sys input = lambda: sys.stdin.readline().rstrip() class AVLNodeSet: __slots__ = ('key', 'size', 'left', 'right', 'balance') def __init__(self, key): self.key = key self.size = 1 self.left = None self.right = None self.balance = 0 class AVLTreeSet: __slots__ = ('node', '__iter') __LEFT, __RIGHT = 1, -1 def __init__(self, V=[]) -> None: # Make a new AVLTree. # V: Iterable self.node = None self.__build(V) def __build(self, V) -> None: for v in sorted(V): self.add(v) def __rotate_L(self, node: AVLNodeSet) -> AVLNodeSet: u = node.left u.size = node.size node.size -= 1 if u.left is None else u.left.size + 1 node.left = u.right u.right = node if u.balance == 1: u.balance, node.balance = 0, 0 else: u.balance, node.balance = -1, 1 return u def __rotate_R(self, node: AVLNodeSet) -> AVLNodeSet: u = node.right u.size = node.size node.size -= 1 if u.right is None else u.right.size + 1 node.right = u.left u.left = node if u.balance == -1: u.balance, node.balance = 0, 0 else: u.balance, node.balance = 1, -1 return u def __update_balance(self, node: AVLNodeSet) -> None: # nodeはnew_node if node.balance == 1: node.right.balance, node.left.balance = -1, 0 elif node.balance == -1: node.right.balance, node.left.balance = 0, 1 else: node.right.balance, node.left.balance = 0, 0 node.balance = 0 def __rotate_LR(self, node: AVLNodeSet) -> AVLNodeSet: # A E # / \ / \ # B C -> B A # /\ /\ /\ # D E D F1F2 C # /\ # F1 F2 # # node: A B = node.left E = B.right E.size = node.size ers = 0 if E.right is None else E.right.size node.size -= B.size - ers B.size -= ers + 1 B.right = E.left E.left = B node.left = E.right E.right = node self.__update_balance(E) return E def __rotate_RL(self, node: AVLNodeSet) -> AVLNodeSet: C = node.right D = C.left D.size = node.size dls = 0 if D.left is None else D.left.size node.size -= C.size - dls C.size -= dls + 1 C.left = D.right D.right = C node.right = D.left D.left = node self.__update_balance(D) return D def add(self, key) -> bool: '''add key. / O(logN)''' if self.node is None: self.node = AVLNodeSet(key) return True pnode = self.node path = [] while pnode is not None: if key < pnode.key: path.append((pnode, self.__LEFT)) pnode = pnode.left elif key > pnode.key: path.append((pnode, self.__RIGHT)) pnode = pnode.right else: return False pnode, di = path[-1] if di == self.__LEFT: pnode.left = AVLNodeSet(key) else: pnode.right = AVLNodeSet(key) while path: new_node = None pnode, di = path.pop() pnode.size += 1 pnode.balance += di if pnode.balance == 0: break if pnode.balance == 2: # pnodeの左部分木が茂りすぎ if pnode.left.balance == -1: # LR2重回転: nodeの右側が茂っている場合 new_node = self.__rotate_LR(pnode) else: # LL1重回転: nodeの左側が茂っている場合 new_node = self.__rotate_L(pnode) break elif pnode.balance == -2: # pnodeの右部分木が茂りすぎ if pnode.right.balance == 1: # RL2重回転: nodeの左側が茂っている場合 new_node = self.__rotate_RL(pnode) else: # RR1重回転: nodeの右側が茂っている場合 new_node = self.__rotate_R(pnode) break # else: 最初にpnode.balanceを更新したので、何もせずcontinueしてOK if new_node is not None: if path: gnode, gdi = path.pop() gnode.size += 1 if gdi == self.__LEFT: gnode.left = new_node else: gnode.right = new_node else: self.node = new_node return while path: path.pop()[0].size += 1 return True def remove(self, key) -> bool: '''Remove key. / O(logN)''' if self.discard(key): return True raise KeyError(f'{key} is not exist.') def discard(self, key) -> bool: '''Discard key. / O(logN)''' path = [] node = self.node while node is not None: if key < node.key: path.append((node, self.__LEFT)) node = node.left elif key > node.key: path.append((node, self.__RIGHT)) node = node.right else: break else: return False if node.left is not None and node.right is not None: path.append((node, self.__LEFT)) lmax = node.left while lmax.right is not None: path.append((lmax, self.__RIGHT)) lmax = lmax.right node.key = lmax.key node = lmax cnode = node.right if node.left is None else node.left if path: pnode, di = path[-1] if di == self.__LEFT: pnode.left = cnode else: pnode.right = cnode else: self.node = cnode return True while path: new_node = None pnode, di = path.pop() pnode.balance -= di pnode.size -= 1 if pnode.balance == 2: if pnode.left.balance < 0: new_node = self.__rotate_LR(pnode) else: new_node = self.__rotate_L(pnode) elif pnode.balance == -2: if pnode.right.balance > 0: new_node = self.__rotate_RL(pnode) else: new_node = self.__rotate_R(pnode) elif pnode.balance != 0: break if new_node is not None: if not path: self.node = new_node return gnode, gdir = path[-1] if gdir == self.__LEFT: gnode.left = new_node else: gnode.right = new_node if new_node.balance != 0: break while path: path.pop()[0].size -= 1 return True def count(self, key) -> int: '''Return the number of key. / O(logN)''' return 1 if key in self else 0 def le(self, key): '''Find the largest element <= key, or None if it doesn't exist. / O(logN)''' res = None node = self.node while node is not None: if key < node.key: node = node.left elif key > node.key: res = node.key node = node.right else: res = node.key break return res def lt(self, key): '''Find the largest element < key, or None if it doesn't exist. / O(logN)''' res = None node = self.node while node is not None: if key < node.key: node = node.left elif key > node.key: res = node.key node = node.right else: break return res def ge(self, key): '''Find the smallest element >= key, or None if it doesn't exist. / O(logN)''' res = None node = self.node while node is not None: if key < node.key: res = node.key node = node.left elif key > node.key: node = node.right else: res = node.key break return res def gt(self, key): '''Find the smallest element > key, or None if it doesn't exist. / O(logN)''' res = None node = self.node while node is not None: if key < node.key: res = node.key node = node.left elif key > node.key: node = node.right else: break return res def index(self, key) -> int: '''Count the number of elements < key. / O(logN)''' indx = 0 node = self.node while node: if key < node.key: node = node.left elif key > node.key: indx += 1 if node.left is None else node.left.size + 1 node = node.right else: indx += 0 if node.left is None else node.left.size break return indx def index_right(self, key) -> int: '''Count the number of elements <= key. / O(logN)''' indx = 0 node = self.node while node: if key < node.key: node = node.left elif key > node.key: indx += 1 if node.left is None else node.left.size + 1 node = node.right else: indx += 1 if node.left is None else node.left.size + 1 break return indx def pop(self, p=-1): '''Return and Remove max element or a[p]. / O(logN)''' if p < 0: p += self.__len__() x = self.__kth_elm(p) self.discard(x) return x def popleft(self): '''Return and Remove min element. / O(logN)''' return self.pop(0) def __kth_elm(self, k): if k < 0: k += self.__len__() now = 0 node = self.node while node is not None: t = now if node.left is None else now + node.left.size if t < k: now = t + 1 node = node.right elif t > k: node = node.left else: return node.key raise IndexError(f'k={k}, len={self.__len__()}') def __contains__(self, x): node = self.node while node: if x < node.key: node = node.left elif x > node.key: node = node.right else: return True return False def __getitem__(self, x): return self.__kth_elm(x) def __iter__(self): self.__iter = 0 return self def __next__(self): if self.__iter == self.__len__(): raise StopIteration res = self.__getitem__(self.__iter) self.__iter += 1 return res def __reversed__(self): for i in range(self.__len__()): yield self.__getitem__(-i-1) def __len__(self): return 0 if self.node is None else self.node.size def __bool__(self): return self.node is not None def __repr__(self): return '{' + ', '.join(map(str, self)) + '}' def __str__(self): return '{' + ', '.join(map(str, self)) + '}' # ----------------------- # n = int(input()) S = list(map(int, input())) T = list(map(int, input())) comp = [i for i in range(n) if S[i] != T[i]] avl = AVLTreeSet(comp) q = int(input()) for _ in range(q): c, x, y = input().split() x, y = int(x), int(y) x -= 1 if c == 'S': S[x] = y else: T[x] = y if S[x] != T[x]: avl.add(x) else: avl.discard(x) if avl: keta = avl[0] if S[keta] < T[keta]: print('<') else: print('>') else: print('=')