import java.util.Comparator; import java.util.Random; import java.util.Scanner; public class Main { public static void main(String[] args) { try (Scanner in = new Scanner(System.in)) { int n = in.nextInt(); int k = in.nextInt() - 1; int q = in.nextInt(); MyTreap tree = new MyTreap((o1, o2) -> Long.compare(o1.longValue(), o2.longValue())); for (int i = 0; i < n; i++) { tree.add(in.nextLong()); } for (int _q = 0; _q < q; _q++) { int m = in.nextInt(); if (m == 1) { long x = in.nextLong(); tree.add(x); } else if (m == 2) { long y = in.nextLong(); long removed = tree.remove(k).longValue(); tree.add(removed + y); } else if (m == 3) { System.out.println(tree.get(k)); } } } } } class MyTreap { private class Node { private Node l; private Node r; private int priority; private T value; private int size; public Node(T value) { super(); this.priority = rand.nextInt(); this.value = value; this.size = 1; } } private static final Random rand = new Random(System.nanoTime()); private Comparator comparator; private Node root; public MyTreap(Comparator comparator) { this.comparator = comparator; } public T get(int index) { return get(root, index); } private T get(Node node, int index) { if (node == null) { return null; } int sizeNodeL = sz(node.l); if (index == sizeNodeL) { return node.value; } else if (index < sizeNodeL) { return get(node.l, index); } else { return get(node.r, index - 1 - sizeNodeL); } } public void add(T value) { root = add(root, new Node(value)); } private Node add(Node node, Node add) { if (node == null) { return add; } int compare = comparator.compare(add.value, node.value); if (compare <= 0) { node.l = add(node.l, add); } else { node.r = add(node.r, add); } node.size++; if (compare <= 0) { if (node.l.priority < node.priority) { node = rotateR(node); } } else { if (node.r.priority < node.priority) { node = rotateL(node); } } return node; } public void remove(T value) { root = remove(root, value); } private Node remove(Node node, T value) { if (node == null) { return null; } int compare = comparator.compare(value, node.value); if (compare == 0) { node = remove(node); if (node == null) { return node; } } else if (compare < 0) { node.l = remove(node.l, value); } else { node.r = remove(node.r, value); } node.size = size(node); return node; } private Node remove(Node node) { if (node.l == null && node.r == null) { clear(node); return null; } Node rotate; if (node.r == null || (node.l != null && node.l.priority <= node.r.priority)) { rotate = rotateR(node); rotate.r = remove(node); } else { rotate = rotateL(node); rotate.l = remove(node); } rotate.size--; return rotate; } public T remove(int index) { T value = get(index); remove(value); return value; } public boolean contains(T value) { return contains(root, value); } private boolean contains(Node node, T value) { if (node == null) { return false; } int compare = comparator.compare(value, node.value); if (compare == 0) { return true; } else if (compare < 0) { return contains(node.l, value); } else { return contains(node.r, value); } } public int indexOf(T value) { return indexOf(root, value, 0); } private int indexOf(Node node, T value, int index) { if (node == null) { return -1; } int compare = comparator.compare(value, node.value); if (compare == 0) { int indexL = indexOf(node.l, value, index); return indexL != -1 ? indexL : (index + sz(node.l)); } else if (compare < 0) { return indexOf(node.l, value, index); } else { return indexOf(node.r, value, index + 1 + sz(node.l)); } } public int indexOfIfExists(T value) { return indexOfIfExists(root, value, 0); } private int indexOfIfExists(Node node, T value, int index) { if (node == null) { return index; } int compare = comparator.compare(value, node.value); // if (compare == 0) { // int indexL = indexOfIfExists(node.l, value, index); // return indexL != -1 ? indexL : (index + sz(node.l)); // } else if (compare <= 0) { return indexOfIfExists(node.l, value, index); } else { return indexOfIfExists(node.r, value, index + 1 + sz(node.l)); } } public int lastIndexOf(T value) { return lastIndexOf(root, value, 0); } private int lastIndexOf(Node node, T value, int index) { if (node == null) { return -1; } int compare = comparator.compare(value, node.value); if (compare == 0) { int indexR = lastIndexOf(node.r, value, index + 1 + sz(node.l)); return indexR != -1 ? indexR : (index + sz(node.l)); } else if (compare < 0) { return lastIndexOf(node.l, value, index); } else { return lastIndexOf(node.r, value, index + 1 + sz(node.l)); } } public int lastIndexOfIfExists(T value) { return lastIndexOfIfExists(root, value, 0); } private int lastIndexOfIfExists(Node node, T value, int index) { if (node == null) { return index; } int compare = comparator.compare(value, node.value); // if (compare == 0) { // int indexR = lastIndexOfIfExists(node.r, value, index + 1 + sz(node.l)); // return indexR != -1 ? indexR : (index + sz(node.l)); // } else if (compare < 0) { return lastIndexOfIfExists(node.l, value, index); } else { return lastIndexOfIfExists(node.r, value, index + 1 + sz(node.l)); } } private Node rotateR(Node node) { Node l = node.l; Node lr = l.r; node.l = lr; l.r = node; node.size = size(node); l.size = size(l); return l; } private Node rotateL(Node node) { Node r = node.r; Node rl = r.l; node.r = rl; r.l = node; node.size = size(node); r.size = size(r); return r; } private int size(Node node) { if (node == null) { return 0; } return 1 + sz(node.l) + sz(node.r); } public int size() { return sz(root); } private int sz(Node node) { return node == null ? 0 : node.size; } public boolean isEmpty() { return size() <= 0; } private void clear(Node node) { node.value = null; node.l = null; node.r = null; node = null; } public void print() { print(root, 0); System.err.println(); } private void print(Node node, int depth) { if (node == null) { return; } print(node.l, depth + 1); for (int i = 0; i < depth; i++) { System.err.print(" "); } System.err.println(node.value + " " + node.size + " " + node.priority); print(node.r, depth + 1); } }