King Kog got annoyed of the usual laxity of his knights — they can break into his hall without prior notice! Thus, the King decided to build a reception with a queue where each knight chooses in advance the time when he will come and how long the visit will take. The knights are served in the order of the recorded time, but each knight has to wait until the visits of all the knights before him are finished.

Princess Keabeanie wants to see her father. However, she does not want to interrupt the knights so she joins the queue. Unfortunately, the knights change their minds very often — they can join the queue or cancel their visits. Please help the princess to understand how long she will have to wait until she sees her father if she enters the queue at the specified moments of time given the records at the reception.

Input

The first line of the input contains a single integer q (1 ≤ q ≤ 3 ⋅ 10^5) — the number of events. An event can be of three types: join, cancel, or query.

  * Join "+ t d" (1 ≤ t, d ≤ 10^6) — a new knight joins the queue, where t is the time when the knight will come and d is the duration of the visit.
  * Cancel "- i" (1 ≤ i ≤ q) — the knight cancels the visit, where i is the number (counted starting from one) of the corresponding join event in the list of all events.
  * Query "? t" (1 ≤ t ≤ 10^6) — Keabeanie asks how long she will wait if she comes at the time t. 



It is guaranteed that after each event there are no two knights with the same entrance time in the queue. Cancel events refer to the previous joins that were not cancelled yet.

Keabeanie can come at the same time as some knight, but Keabeanie is very polite and she will wait for the knight to pass.

Output

For each query write a separate line with the amount of time Keabeanie will have to wait.

Example

Input


19
? 3
+ 2 2
? 3
? 4
+ 5 2
? 5
? 6
+ 1 2
? 2
? 3
? 4
? 5
? 6
? 7
? 9
- 8
? 2
? 3
? 6


Output


0
1
0
2
1
3
2
1
2
1
0
0
2
1
1
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    FastScanner in;
    PrintWriter out;

    public static void main(String[] args) throws Exception {
        (new Main()).run();
    }

    private void run() throws Exception {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    private void solve() throws Exception {
        int q = in.nextInt();
        int[] queries = new int[q + 1];
        Tree tree = new Tree(1_000_500);
        for (int i = 1; i <= q; i++) {
            char command = in.next().charAt(0);
            int t = in.nextInt();
            queries[i] = t;
            switch (command) {
                case '+':
                    int d = in.nextInt();
                    tree.join(t, d);
                    break;
                case '-':
                    tree.cancel(queries[t]);
                    break;
                case '?':
                    out.println(tree.getWaitingTime(t));
                    break;
            }
        }
    }


    private class Tree {
        private Node root;

        public Tree(int maxSize) {
            this.root = buildEmptyTree(0, maxSize);
        }

        public void join(int t, int d) {
            join(root, t, d);
        }

        public void cancel(int t) {
            join(t, 0);
        }

        public long getWaitingTime(int time) {
            Node node = root;
            long result = 0;
            while (!node.isLeaf()) {
                Node leftSon = node.getLeftSon();
                Node rightSon = node.getRightSon();
                if (time < node.getMid()) {
                    node = leftSon;
                } else {
                    result = Math.max(0, result - leftSon.getGiveTime());
                    result += leftSon.getTakeTime();
                    node = rightSon;
                }
            }
            result += node.getTakeTime() + 1 - node.getGiveTime();
            return result;
        }

        private void join(Node node, int t, int d) {
            if (node.getLeftBorder() <= t && t < node.getRightBorder()) {
                if (node.isLeaf()) {
                    if (d == 0) {
                        node.setTakeTime(0);
                        node.setGiveTime(1);
                    } else {
                        node.setTakeTime(d - 1);
                        node.setGiveTime(0);
                    }
                } else {
                    join(node.getLeftSon(), t, d);
                    join(node.getRightSon(), t, d);
                    fixNode(node);
                }
            }
        }

        private void fixNode(Node node) {
            if (!node.isLeaf()) {
                Node leftSon = node.getLeftSon();
                Node rightSon = node.getRightSon();
                long giveTime = leftSon.getGiveTime() + Math.max(0, rightSon.getGiveTime() - leftSon.getTakeTime());
                long takeTime = rightSon.getTakeTime() + Math.max(0, leftSon.getTakeTime() - rightSon.getGiveTime());
                node.setGiveTime(giveTime);
                node.setTakeTime(takeTime);
            }
        }

        private Node buildEmptyTree(int leftBorder, int rightBorder) {
            Node node = new Node(leftBorder, rightBorder);
            if (!node.isLeaf()) {
                int mid = node.getMid();
                node.setLeftSon(buildEmptyTree(leftBorder, mid));
                node.setRightSon(buildEmptyTree(mid, rightBorder));
            }
            return node;
        }

    }

    private class Node {
        private int leftBorder;
        private int rightBorder;
        //Segment can be empty at the beginning, so it give time to previous segment
        private long giveTime;
        //Segment can take time from next segment to end all meetings.
        private long takeTime;
        private Node leftSon;
        private Node rightSon;
        private boolean isLeaf;

        public Node(int leftBorder, int rightBorder) {
            this.leftBorder = leftBorder;
            this.rightBorder = rightBorder;
            this.giveTime = rightBorder - leftBorder;
            isLeaf = (giveTime == 1);
            this.takeTime = 0;
        }

        public Node getLeftSon() {
            return leftSon;
        }

        public void setLeftSon(Node leftSon) {
            this.leftSon = leftSon;
        }

        public Node getRightSon() {
            return rightSon;
        }

        public void setRightSon(Node rightSon) {
            this.rightSon = rightSon;
        }

        public boolean isLeaf() {
            return isLeaf;
        }

        public int getLeftBorder() {
            return leftBorder;
        }

        public int getRightBorder() {
            return rightBorder;
        }

        public long getGiveTime() {
            return giveTime;
        }

        public void setGiveTime(long giveTime) {
            this.giveTime = giveTime;
        }

        public long getTakeTime() {
            return takeTime;
        }

        public void setTakeTime(long takeTime) {
            this.takeTime = takeTime;
        }

        public int getMid() {
            return (leftBorder + rightBorder) / 2;
        }

        @Override
        public String toString() {
            return String.format("" +
                            "###############\n" +
                            "LeftBorder = %d;\n" +
                            "RightBorder = %d;\n" +
                            "GiveTime = %d;\n" +
                            "TakeTime = %d;\n" +
                            "IsLeaf = %b" +
                            "##############\n",
                    leftBorder,
                    rightBorder,
                    giveTime,
                    takeTime,
                    isLeaf
            );
        }
    }

    private class FastScanner {
        BufferedReader bufferedReader;
        StringTokenizer stringTokenizer;

        public FastScanner(InputStream inputStream) {
            this.bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String next() throws IOException {
            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                String line = bufferedReader.readLine();
                if (line == null) {
                    throw new EOFException("End of input stream is reached.");
                }
                stringTokenizer = new StringTokenizer(line);
            }
            return stringTokenizer.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}