# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py import math from bisect import bisect_left, bisect_right from collections.abc import Iterable, Iterator from typing import Generic, TypeVar class EulerTour: n: int tree: list[list[int]] _result: list[int] | None = None def __init__(self, n: int): self.n = n self.tree = [[] for _ in range(n)] def add_edge(self, u: int, v: int): self.tree[u].append(v) self.tree[v].append(u) def build(self, root: int = 0): self._dfs(root) def _dfs(self, root: int): if self._result: return result: list[int] = [] IN, OUT = 0, 1 stack = [(root, float("NaN"), IN)] while stack: curr, prev, order = stack.pop() if order == IN: result.append(curr) stack.append((curr, prev, OUT)) for to in self.tree[curr]: if to == prev: continue stack.append((to, curr, IN)) else: result.append(curr) self._result = result def order(self) -> list[int]: assert self._result is not None return self._result def begin_end(self) -> tuple[list[int], list[int]]: assert self._result is not None begin = [-1] * self.n end = [-1] * self.n for i, v in enumerate(self._result): if begin[v] == -1: begin[v] = i else: end[v] = i return begin, end class LowestCommonAncestor: """ Lowest Common Ancestor (LCA) --- 木に対する最小共通祖先を求めるデータ構造 """ def __init__(self, n: int): """\ 木の頂点数 n を指定して初期化する Parameters: n (int): 木の頂点数 """ self._n = n self._logn = n.bit_length() + 1 self._depth = [0] * self._n self._distance = [0] * self._n self._ancestor = [-1 for _ in range(self._n * self._logn)] self._edges = [[] for _ in range(self._n)] def add_edge(self, u: int, v: int, w: int = 1): """\ u, v 間に重み w の辺を追加する Parameters: u (int): 辺の片方の頂点 v (int): 辺のもう片方の頂点 w (int): 辺の重み """ self._edges[u].append((v, w)) self._edges[v].append((u, w)) def build(self, root: int = 0): """\ 根を root にした木を構築する Parameters: root (int): 根の頂点番号 """ stack = [root] while stack: now = stack.pop() for to, w in self._edges[now]: if self._ancestor[to] == now or self._ancestor[now] == to: continue self._ancestor[to] = now self._depth[to] = self._depth[now] + 1 self._distance[to] = self._distance[now] + w stack.append(to) for k in range(1, self._logn): for i in range(self._n): if self._ancestor[(k - 1) * self._n + i] == -1: self._ancestor[k * self._n + i] = -1 else: double = (k - 1) * self._n + self._ancestor[(k - 1) * self._n + i] self._ancestor[k * self._n + i] = self._ancestor[double] def lca(self, u: int, v: int) -> int: """\ u, v の最小共通祖先を求める Parameters: u (int): 頂点 u v (int): 頂点 v Returns: lca (int): u, v の最小共通祖先 """ # u の深さを v の深さ以下になるよう調整する if self._depth[u] > self._depth[v]: u, v = v, u # v の深さを u に合わせる for k in range(self._logn - 1, -1, -1): if ((self._depth[v] - self._depth[u]) >> k) & 1 == 1: v = self._ancestor[k * self._n + v] # この時点で一致すれば、それが解 if u == v: return u # u, v がギリギリ一致しないよう親方向に辿る for k in range(self._logn - 1, -1, -1): if self._ancestor[k * self._n + u] != self._ancestor[k * self._n + v]: u = self._ancestor[k * self._n + u] v = self._ancestor[k * self._n + v] # 最後に 1 ステップ親方向に辿った頂点が解 return self._ancestor[u] # u, v (0-indexed) の距離を求める def distance(self, u: int, v: int) -> int: """\ u, v 間の距離を求める Parameters: u (int): 頂点 u v (int): 頂点 v Returns: dist (int): u, v 間の最短距離の長さ """ return self._distance[u] + self._distance[v] - 2 * self._distance[self.lca(u, v)] # v の親を求める def parent(self, v: int) -> int: """\ v の親を求める Parameters: v (int): 頂点 v Returns: parent (int): 頂点 v の親 """ return self._ancestor[v] def ancestor(self, v: int, gen: int) -> int: if self._depth[v] < gen: return None curr = v for i in range(self._logn): if (gen >> i) & 1 == 1: curr = self._ancestor[i * self._n + curr] return curr T = TypeVar("T") class SortedSet(Generic[T]): BUCKET_RATIO = 16 SPLIT_RATIO = 24 def __init__(self, a: Iterable[T] = []) -> None: "Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)" a = list(a) n = len(a) if any(a[i] > a[i + 1] for i in range(n - 1)): a.sort() if any(a[i] >= a[i + 1] for i in range(n - 1)): a, b = [], a for x in b: if not a or a[-1] != x: a.append(x) n = self.size = len(a) num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO))) self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)] def __iter__(self) -> Iterator[T]: for i in self.a: for j in i: yield j def __reversed__(self) -> Iterator[T]: for i in reversed(self.a): for j in reversed(i): yield j def __eq__(self, other) -> bool: return list(self) == list(other) def __len__(self) -> int: return self.size def __repr__(self) -> str: return "SortedSet" + str(self.a) def __str__(self) -> str: s = str(list(self)) return "{" + s[1 : len(s) - 1] + "}" def _position(self, x: T) -> tuple[list[T], int, int]: "return the bucket, index of the bucket and position in which x should be. self must not be empty." for i, a in enumerate(self.a): if x <= a[-1]: break return (a, i, bisect_left(a, x)) def __contains__(self, x: T) -> bool: if self.size == 0: return False a, _, i = self._position(x) return i != len(a) and a[i] == x def add(self, x: T) -> bool: "Add an element and return True if added. / O(√N)" if self.size == 0: self.a = [[x]] self.size = 1 return True a, b, i = self._position(x) if i != len(a) and a[i] == x: return False a.insert(i, x) self.size += 1 if len(a) > len(self.a) * self.SPLIT_RATIO: mid = len(a) >> 1 self.a[b : b + 1] = [a[:mid], a[mid:]] return True def _pop(self, a: list[T], b: int, i: int) -> T: ans = a.pop(i) self.size -= 1 if not a: del self.a[b] return ans def discard(self, x: T) -> bool: "Remove an element and return True if removed. / O(√N)" if self.size == 0: return False a, b, i = self._position(x) if i == len(a) or a[i] != x: return False self._pop(a, b, i) return True def lt(self, x: T) -> T | None: "Find the largest element < x, or None if it doesn't exist." for a in reversed(self.a): if a[0] < x: return a[bisect_left(a, x) - 1] def le(self, x: T) -> T | None: "Find the largest element <= x, or None if it doesn't exist." for a in reversed(self.a): if a[0] <= x: return a[bisect_right(a, x) - 1] def gt(self, x: T) -> T | None: "Find the smallest element > x, or None if it doesn't exist." for a in self.a: if a[-1] > x: return a[bisect_right(a, x)] def ge(self, x: T) -> T | None: "Find the smallest element >= x, or None if it doesn't exist." for a in self.a: if a[-1] >= x: return a[bisect_left(a, x)] def __getitem__(self, i: int) -> T: "Return the i-th element." if i < 0: for a in reversed(self.a): i += len(a) if i >= 0: return a[i] else: for a in self.a: if i < len(a): return a[i] i -= len(a) raise IndexError def pop(self, i: int = -1) -> T: "Pop and return the i-th element." if i < 0: for b, a in enumerate(reversed(self.a)): i += len(a) if i >= 0: return self._pop(a, ~b, i) else: for b, a in enumerate(self.a): if i < len(a): return self._pop(a, b, i) i -= len(a) raise IndexError def index(self, x: T) -> int: "Count the number of elements < x." ans = 0 for a in self.a: if a[-1] >= x: return ans + bisect_left(a, x) ans += len(a) return ans def index_right(self, x: T) -> int: "Count the number of elements <= x." ans = 0 for a in self.a: if a[-1] > x: return ans + bisect_right(a, x) ans += len(a) return ans LIMIT = 10**12 def golden(i): ok, ng = -1, LIMIT while abs(ok - ng) > 1: mid = (ok + ng) // 2 if i**2 * 5 >= (2 * mid - i) ** 2: ok = mid else: ng = mid return ok def golden_2(i): ok, ng = -1, LIMIT while abs(ok - ng) > 1: mid = (ok + ng) // 2 if i**2 * 5 >= (2 * mid - 3 * i) ** 2: ok = mid else: ng = mid return ok N, R, B = [int(s) for s in input().split()] red_edges = [] blue_edges = [] for u in range(1, N + 1): v = golden(u) if u < v <= N: red_edges.append((u - 1, v - 1)) v = golden_2(u) if u < v <= N: blue_edges.append((u - 1, v - 1)) euler = EulerTour(N) for u, v in red_edges + blue_edges: euler.add_edge(u, v) euler.build() begin, end = euler.begin_end() inv_begin = [0] * (2 * N) for i in range(N): inv_begin[begin[i]] = i sset = SortedSet() red = LowestCommonAncestor(N) blue = LowestCommonAncestor(N) for u, v in red_edges: red.add_edge(u, v, 1) blue.add_edge(u, v, 0) for u, v in blue_edges: red.add_edge(u, v, 0) blue.add_edge(u, v, 1) red.build() blue.build() ans_red = 0 ans_blue = 0 Q = int(input()) for _ in range(Q): cmd, x = [int(s) for s in input().split()] if cmd == 1: x -= 1 if len(sset) == 0: print(0) sset.add(begin[x]) continue l = sset.lt(begin[x]) if l is None: l = sset[-1] r = sset.gt(begin[x]) if r is None: r = sset[0] l, r = inv_begin[l], inv_begin[r] if begin[x] in sset: ans_red -= red.distance(l, x) + red.distance(x, r) - red.distance(l, r) ans_blue -= blue.distance(l, x) + blue.distance(x, r) - blue.distance(l, r) sset.discard(begin[x]) else: ans_red += red.distance(l, x) + red.distance(x, r) - red.distance(l, r) ans_blue += blue.distance(l, x) + blue.distance(x, r) - blue.distance(l, r) sset.add(begin[x]) elif cmd == 2: R = x else: B = x print((ans_red * R + ans_blue * B) // 2)