package main import ( "bufio" "fmt" "os" "strconv" ) func getNextString(scanner *bufio.Scanner) string { if !scanner.Scan() { panic("scan failed") } return scanner.Text() } func atoi(s string) int { x, _ := strconv.Atoi(s); return x } func getNextInt(scanner *bufio.Scanner) int { return atoi(getNextString(scanner)) } func atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x } func getNextInt64(scanner *bufio.Scanner) int64 { return atoi64(getNextString(scanner)) } func atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x } func getNextFloat64(scanner *bufio.Scanner) float64 { return atof64(getNextString(scanner)) } func main() { fp := os.Stdin wfp := os.Stdout extra := 0 if os.Getenv("I") == "IronMan" { fp, _ = os.Open(os.Getenv("END_GAME")) extra = 100 } scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 1000005), 1000005) writer := bufio.NewWriter(wfp) defer func() { r := recover() if r != nil { fmt.Fprintln(writer, r) } writer.Flush() }() solve(scanner, writer) for i := 0; i < extra; i++ { fmt.Fprintln(writer, "-----------------------------------") solve(scanner, writer) } } func solve(scanner *bufio.Scanner, writer *bufio.Writer) { n := getNextInt(scanner) s := getNextString(scanner) t := getNextString(scanner) q := getNextInt(scanner) ss := make([]int, n) tt := make([]int, n) tr := newTreeWithIntComparator() for i := 0; i < n; i++ { ss[i] = int(s[i] - '0') tt[i] = int(t[i] - '0') if ss[i] != tt[i] { tr.Put(i, 1) } } for q > 0 { q-- c := getNextString(scanner) x := getNextInt(scanner) - 1 y := getNextInt(scanner) if c == "S" { ss[x] = y } else { tt[x] = y } if ss[x] == tt[x] { tr.Remove(x) } else { tr.Put(x, 1) } if tr.Empty() { fmt.Fprintln(writer, "=") continue } first := tr.Left().Key.(int) if ss[first] < tt[first] { fmt.Fprintln(writer, "<") continue } fmt.Fprintln(writer, ">") } } func max(a, b int) int { if a < b { return b } return a } func min(a, b int) int { return -max(-a, -b) } func abs(a int) int { return max(a, -a) } type tree struct { Root *node Comparator func(a, b interface{}) int allowMultiKey bool } type node struct { Left, Right, Parent *node Key interface{} Value interface{} size int } func newTreeWithIntComparator() *tree { return newTree(func(a, b interface{}) int { aa := a.(int) bb := b.(int) switch { case aa < bb: return -1 case aa > bb: return 1 } return 0 }) } func newTree(comparator func(interface{}, interface{}) int) *tree { return &tree{Root: nil, Comparator: comparator} } func newMultiKeyTree(comparator func(interface{}, interface{}) int) *tree { return &tree{Root: nil, Comparator: comparator, allowMultiKey: true} } func newNode(parent *node, key, value interface{}) *node { return &node{Parent: parent, Key: key, Value: value, size: 1} } func (n *node) IsRoot() bool { return n.Parent == nil } func (n *node) IsLeft() bool { return !n.IsRoot() && n.Parent.Left == n } func (n *node) IsRight() bool { return !n.IsRoot() && n.Parent.Right == n } func (n *node) Update() { n.size = 1 + n.Left.Size() + n.Right.Size() } func (n *node) Size() int { if n == nil { return 0 } return n.size } func (n *node) MaximumNode() *node { if n == nil { return n } if n.Right == nil { return n } return n.Right.MaximumNode() } func (n *node) MinimumNode() *node { if n == nil { return n } if n.Left == nil { return n } return n.Left.MinimumNode() } func (n *node) AppendLeft(m *node) { if n == nil { return } n.Left = m n.Update() if m == nil { return } m.Parent = n } func (n *node) AppendRight(m *node) { if n == nil { return } n.Right = m n.Update() if m == nil { return } m.Parent = n } func (n *node) Next() *node { if n.Right != nil { return n.Right.MinimumNode() } for n.IsRight() { n = n.Parent } if n.IsLeft() { return n.Parent } return nil } func (n *node) Prev() *node { if n.Left != nil { return n.Left.MaximumNode() } for n.IsLeft() { n = n.Parent } if n.IsRight() { return n.Parent } return nil } func (t *tree) Put(key, value interface{}) { if t.Root == nil { t.Root = newNode(nil, key, value) return } now := t.Root for { compared := t.Comparator(key, now.Key) if compared < 0 { if now.Left == nil { now.Left = newNode(now, key, value) t.Update(now) return } now = now.Left continue } if compared > 0 || t.allowMultiKey { if now.Right == nil { now.Right = newNode(now, key, value) t.Update(now) return } now = now.Right continue } now.Value = value break } } func (t *tree) Get(key interface{}) (interface{}, bool) { now := t.Lookup(key) if now == nil { return nil, false } return now.Value, true } func (t *tree) Lookup(key interface{}) *node { now := t.Root for now != nil { compared := t.Comparator(key, now.Key) switch { case compared == 0: return now case compared < 0: now = now.Left case compared > 0: now = now.Right } } return nil } func (t *tree) Remove(key interface{}) { now := t.Lookup(key) if now == nil { return } for now.Size() > 1 { if now.Left.Size() > now.Right.Size() { t.Rotate(now.Left) continue } t.Rotate(now.Right) } parent := now.Parent switch { case now.IsRoot(): t.Root = nil case now.IsLeft(): parent.Left = nil case now.IsRight(): parent.Right = nil } for parent != nil { parent.Update() parent = parent.Parent } } func (t *tree) Update(now *node) { for now != nil { now.Update() parent := now.Parent switch { case now.Left.Size() > now.Right.Size(): t.Rotate(now.Left) case now.Left.Size() < now.Right.Size(): t.Rotate(now.Right) } now = parent } } func (t *tree) Rotate(now *node) { parent := now.Parent grand := parent.Parent switch { case now.IsRight(): parent.AppendRight(now.Left) now.AppendLeft(parent) case now.IsLeft(): parent.AppendLeft(now.Right) now.AppendRight(parent) } switch { case grand == nil: t.Root = now now.Parent = nil case grand.Left == parent: grand.AppendLeft(now) case grand.Right == parent: grand.AppendRight(now) } } func (t *tree) Right() *node { return t.Root.MaximumNode() } func (t *tree) Left() *node { return t.Root.MinimumNode() } func (t *tree) Floor(key interface{}) (*node, bool) { now := t.Root var n *node for now != nil { compared := t.Comparator(key, now.Key) switch { case compared == 0: return now, true case compared < 0: now = now.Left case compared > 0: n = now now = now.Right } } return n, n != nil } func (t *tree) Ceiling(key interface{}) (*node, bool) { now := t.Root var n *node for now != nil { compared := t.Comparator(key, now.Key) switch { case compared == 0: return now, true case compared < 0: n = now now = now.Left case compared > 0: now = now.Right } } return n, n != nil } func (t *tree) Empty() bool { return t.Root == nil } func (t *tree) At(i int) (*node, bool) { var n *node now := t.Root for now != nil && i > 0 { if i <= now.Left.Size() { now = now.Left continue } i -= now.Left.Size() + 1 if i <= 0 { n = now } now = now.Right } return n, n != nil }