import java.io.FileNotFoundException; import java.util.Arrays; import java.util.Scanner; class Main { int N = 100; Scanner sc = new Scanner(System.in); int[] num = new int[N]; AVLTree pnd = new AVLTree(); { for (int i = 0; i < N; ++i) { pnd.insert(i); } } public void run() { int Q = sc.nextInt(); Arrays.fill(num, -1); for (int i = 0; i < N; i += 2) { dfs1(1, pnd.sz + 1, i, i + 1); } for (int i = 0; i < N; ++i) { System.out.print(num[i] / 10 + "" + num[i] % 10); if (num[i] == -1) throw new AssertionError(); System.out.print(i == N - 1 ? "\n" : " "); } } void dfs1(int l, int r, int u, int v) { int lp = (int) pnd.kth(l).key; int mp = (int) pnd.kth((l + r) / 2).key; int rp = (int) pnd.kth(r - 1).key; if (r - l == 1) { throw new AssertionError(); } for (int i = 0; i < N; ++i) { if (num[i] != -1) { System.out.print("??"); } else { if (lp <= i && i < mp) { System.out.print(u / 10 + "" + u % 10); } else if (mp <= i && i <= rp) { System.out.print(v / 10 + "" + v % 10); } else { System.out.print("??"); } } System.out.print(i == N - 1 ? "\n" : " "); } int p0 = sc.nextInt(); int p1 = sc.nextInt(); int p2 = sc.nextInt(); if (p2 == 2) { dfs2(l, (l + r) / 2, (l + r) / 2, r, u, v); } else if (p2 == 1) { int mp2 = (int) pnd.kth((l + (l + r) / 2) / 2).key; for (int i = 0; i < N; ++i) { if (num[i] != -1) { System.out.print("??"); } else { if (mp <= i && i <= rp) { System.out.print(v / 10 + "" + v % 10); } else { System.out.print("??"); } } System.out.print(i == N - 1 ? "\n" : " "); } p0 = sc.nextInt(); p1 = sc.nextInt(); p2 = sc.nextInt(); if (p2 == 1) { dfs1((l + r) / 2, r, u, v); } else if (p2 == 0) { dfs1(l, (l + r) / 2, u, v); } else { throw new AssertionError(); } } else { dfs2(l, (l + r) / 2, (l + r) / 2, r, v, u); } } void dfs2(int l1, int r1, int l2, int r2, int u, int v) { int lp1 = (int) pnd.kth(l1).key; int mp1 = (int) pnd.kth((l1 + r1) / 2).key; int rp1 = (int) pnd.kth(r1 - 1).key; int lp2 = (int) pnd.kth(l2).key; int mp2 = (int) pnd.kth((l2 + r2) / 2).key; int rp2 = (int) pnd.kth(r2 - 1).key; if (r1 - l1 == 1 && r2 - l2 == 1) { num[lp1] = u; num[lp2] = v; pnd.delete(lp1); pnd.delete(lp2); return; } for (int i = 0; i < N; ++i) { if (num[i] != -1) { System.out.print("??"); } else { if (lp1 <= i && i < mp1) { System.out.print(u / 10 + "" + u % 10); } else if (lp2 <= i && i < mp2) { System.out.print(v / 10 + "" + v % 10); } else { System.out.print("??"); } } System.out.print(i == N - 1 ? "\n" : " "); } int p0 = sc.nextInt(); int p1 = sc.nextInt(); int p2 = sc.nextInt(); if (p2 == 2) { dfs2(l1, (l1 + r1) / 2, l2, (l2 + r2) / 2, u, v); } else if (p2 == 1) { for (int i = 0; i < N; ++i) { if (num[i] != -1) { System.out.print("??"); } else { if (mp1 <= i && i <= rp1) { System.out.print(u / 10 + "" + u % 10); } else if (lp2 <= i && i < mp2) { System.out.print(v / 10 + "" + v % 10); } else { System.out.print("??"); } } System.out.print(i == N - 1 ? "\n" : " "); } p0 = sc.nextInt(); p1 = sc.nextInt(); p2 = sc.nextInt(); if (p2 == 2) { dfs2((l1 + r1) / 2, r1, l2, (l2 + r2) / 2, u, v); } else if (p2 == 0) { dfs2(l1, (l1 + r1) / 2, (l2 + r2) / 2, r2, u, v); } else { throw new AssertionError(); } } else { dfs2((l1 + r1) / 2, r1, (l2 + r2) / 2, r2, u, v); } } public static class AVLTree { Node root = null; int sz = 0; Node ceiling(long v) { Node node = root; while (node != null) { if (min(node.right) <= v) { node = node.right; } else if (node.key <= v) return node; else node = node.left; } return node; } Node floor(long v) { Node node = root; while (node != null) { if (max(node.left) >= v) { node = node.left; } else if (node.key >= v) return node; else node = node.right; } return node; } class Node { long key; long max; long min; int height; int balance; int sz = 1; Node left = null; Node right = null; Node parent = null; public Node(long key_, Node parent_) { key = key_; parent = parent_; max = key_; min = key_; } } Node kth(long a) { Node node = root; int sum = 0; while (node != null) { if (sum + node.sz < a) { return null; } if (sum + sz(node.left) + 1 == a) { return node; } if (sum + sz(node.left) + 1 < a) { sum = sum + 1 + sz(node.left); node = node.right; } else { node = node.left; } } return null; } boolean contain(int delKey) { if (root == null) return false; Node node = root; while (node != null) { if (delKey == node.key) { return true; } node = delKey >= node.key ? node.right : node.left; } return false; } boolean delete(long key) { if (root == null) return false; Node node = root; while (node != null) { if (key == node.key) { delete(node); --sz; return true; } node = key >= node.key ? node.right : node.left; } return false; } //boolean delete(long key) から呼び出す。 private void delete(Node node) { if (node.left == null && node.right == null) { if (node.parent == null) { root = null; return; } Node parent = node.parent; if (parent.left == node) parent.left = null; else parent.right = null; rebalance(parent); } if (node.left != null) { Node child = node.left; while (child.right != null) { child = child.right; } node.key = child.key; delete(child); } else if (node.right != null) { Node child = node.right; while (child.left != null) { child = child.left; } node.key = child.key; delete(child); } } boolean insert(long key) { if (root == null) { root = new Node(key, null); ++sz; return true; } Node cur = root; Node parent = null; while (true) { if (cur.key == key) { return false; } parent = cur; boolean goLeft = key < cur.key; cur = goLeft ? cur.left : cur.right; if (cur == null) { if (goLeft) { parent.left = new Node(key, parent); } else { parent.right = new Node(key, parent); } rebalance(parent); break; } } ++sz; return true; } void rebalance(Node n) { setBalance(n); if (n.balance == -2) { if (height(n.left.left) >= height(n.left.right)) { n = rotateRight(n); } else { n = rotateLeftThenRight(n); } } else if (n.balance == 2) { if (height(n.right.right) >= height(n.right.left)) { n = rotateLeft(n); } else { n = rotateRightThenLeft(n); } } if (n.parent != null) { rebalance(n.parent); } else { root = n; } } void setBalance(Node... nodes) { for (Node n : nodes) { n.height = 1 + Math.max(height(n.right), height(n.left)); n.balance = height(n.right) - height(n.left); n.sz = 1 + sz(n.left) + sz(n.right); n.max = Math.max(n != null ? n.key : -Integer.MAX_VALUE, Math.max(max(n.left), max(n.right))); n.min = Math.min(n != null ? n.key : Integer.MAX_VALUE, Math.min(min(n.left), min(n.right))); } } int sz(Node node) { return node != null ? node.sz : 0; } int height(Node node) { return node != null ? node.height : -1; } long max(Node node) { return node != null ? node.max : -Long.MAX_VALUE; } long min(Node node) { return node != null ? node.min : Long.MAX_VALUE; } Node rotateRight(Node a) { Node b = a.left; if (a.parent != null) { if (a.parent.left == a) { a.parent.left = b; } else { a.parent.right = b; } } b.parent = a.parent; a.parent = b; a.left = b.right; b.right = a; if (a.left != null) a.left.parent = a; setBalance(a, b); return b; } Node rotateLeft(Node a) { Node b = a.right; if (a.parent != null) { if (a.parent.right == a) { a.parent.right = b; } else { a.parent.left = b; } } b.parent = a.parent; a.parent = b; a.right = b.left; b.left = a; if (a.right != null) a.right.parent = a; setBalance(a, b); return b; } Node rotateLeftThenRight(Node n) { n.left = rotateLeft(n.left); return rotateRight(n); } Node rotateRightThenLeft(Node n) { n.right = rotateRight(n.right); return rotateLeft(n); } void inOrder(Node cur) { if (cur == null) return; inOrder(cur.left); System.out.println(cur.key); inOrder(cur.right); } } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } public static void main(String[] args) throws FileNotFoundException { new Main().run(); } }