The development of a text editor is a hard problem. You need to implement an extra module for brackets coloring in text.

Your editor consists of a line with infinite length and cursor, which points to the current character. Please note that it points to only one of the characters (and not between a pair of characters). Thus, it points to an index character. The user can move the cursor left or right one position. If the cursor is already at the first (leftmost) position, then it does not move left.

Initially, the cursor is in the first (leftmost) character.

Also, the user can write a letter or brackets (either (, or )) to the position that the cursor is currently pointing at. A new character always overwrites the old value at that position.

Your editor must check, whether the current line is the correct text. Text is correct if the brackets in them form the correct bracket sequence.

Formally, correct text (CT) must satisfy the following rules: 

  * any line without brackets is CT (the line can contain whitespaces); 
  * If the first character of the string — is (, the last — is ), and all the rest form a CT, then the whole line is a CT; 
  * two consecutively written CT is also CT. 



Examples of correct texts: hello(codeforces), round, ((i)(write))edi(tor)s, ( me). Examples of incorrect texts: hello)oops(, round), ((me).

The user uses special commands to work with your editor. Each command has its symbol, which must be written to execute this command.

The correspondence of commands and characters is as follows: 

  * L — move the cursor one character to the left (remains in place if it already points to the first character); 
  * R — move the cursor one character to the right; 
  * any lowercase Latin letter or bracket (( or )) — write the entered character to the position where the cursor is now. 



For a complete understanding, take a look at the first example and its illustrations in the note below.

You are given a string containing the characters that the user entered. For the brackets coloring module's work, after each command you need to:

  * check if the current text in the editor is a correct text; 
  * if it is, print the least number of colors that required, to color all brackets. 



If two pairs of brackets are nested (the first in the second or vice versa), then these pairs of brackets should be painted in different colors. If two pairs of brackets are not nested, then they can be painted in different or the same colors. For example, for the bracket sequence ()(())()() the least number of colors is 2, and for the bracket sequence (()(()())())(()) — is 3.

Write a program that prints the minimal number of colors after processing each command.

Input

The first line contains an integer n (1 ≤ n ≤ 10^6) — the number of commands. 

The second line contains s — a sequence of commands. The string s consists of n characters. It is guaranteed that all characters in a string are valid commands.

Output

In a single line print n integers, where the i-th number is:

  * -1 if the line received after processing the first i commands is not valid text, 
  * the minimal number of colors in the case of the correct text. 

Examples

Input


11
(RaRbR)L)L(


Output


-1 -1 -1 -1 -1 -1 1 1 -1 -1 2 

Input


11
(R)R(R)Ra)c


Output


-1 -1 1 1 -1 -1 1 1 1 -1 1 

Note

In the first example, the text in the editor will take the following form:

  1.     (  
    ^

  2.     (  
     ^

  3.     (a  
     ^

  4.     (a  
      ^

  5.     (ab  
      ^

  6.     (ab  
       ^

  7.     (ab)  
       ^

  8.     (ab)  
      ^

  9.     (a))  
      ^

  10.     (a))  
     ^

  11.     (())  
     ^
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class Editor {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.readInt();
        char[] steps = sc.readString(N).toCharArray();
        int size = 1;
        for (char c : steps) {
            if (c == 'R') {
                size++;
            }
        }
        SegmentTree segTree = new SegmentTree(new int[size]);

        int pos = 0;
        char[] text = new char[size];
        int pair = 0;
        int ans = 0;
        for (char c : steps) {
            if (c == 'R') {
                pos++;
            }
            else if (c == 'L') {
                if (pos > 0) {
                    pos--;
                }
            }
            else {
                // lose what was there
                int add = 0;
                if (text[pos] == '(') {
                    add -= 1;
                    // lost an opening
                }
                else if (text[pos] == ')') {
                    add += 1;
                }

                // Gain what is added
                if (c == '(') {
                    add += 1;
                }
                else if (c == ')') {
                    add -= 1;
                }

                pair += add;
                segTree.updateRange(pos, size - 1, add);
                text[pos] = c;
                ans = -1;
                if (pair == 0 && segTree.queryMin(0, size - 1) >= 0) {
                    // Then it's balanced parens
                    ans = (int) segTree.queryMax(0, size - 1);
                }
            }
            out.print(ans + " ");
        }
        out.close();
    }

    static class SegmentTree {
        // keep track of the lo and hi bounds controlled of a certain node
        int[] lo, hi;
        int[] arr;
        long[] treeMax, lazyMax;
        long[] treeMin, lazyMin;
        long NEUTRAL = (long) -1e9;
        // todo MAKE SURE NEUTRAL IS CORRECT
        int N;

        // Depending on the use case, the segment tree may merge
        // the values of two nodes via adding, xor, etc.
//        public long merge(long leftVal, long rightVal) {
//            return Math.min(leftVal, rightVal);
//        }

        public SegmentTree(int[] arr) {
            N = arr.length;
            this.arr = arr;
            // Oh maybe the reason for 4N is because the delta values
            // won't need to be pushed for the lowest layer of the tree
            // because we won't need to query below them
            lo = new int[4 * N + 1];
            hi = new int[4 * N + 1];
            treeMax = new long[4 * N + 1];
            lazyMax = new long[4 * N + 1];
            treeMin = new long[4 * N + 1];
            lazyMin = new long[4 * N + 1];
            // we had to give up that 0th cell of memory
            // because there's no easy way to go down from it
            buildTree(1, 0, N - 1);
        }

        private void buildTree(int node, int l, int r) {
            if (l == r) {
                treeMax[node] = arr[l];
                treeMin[node] = arr[l];

                lo[node] = l;
                hi[node] = r;
            }
            else {
                lo[node] = l;
                hi[node] = r;
                int mid = (l + r) / 2;
                buildTree(leftChild(node), l, mid);
                buildTree(rightChild(node), mid + 1, r);
                pullUp(node);
            }
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++) {
                sb.append(queryMax(i, i) + " ");
            }
            return sb.toString();
        }

        // The key insight for modifying this is to have a FAST way
        // of updating aggregate information using the deltas.
        // update a node with its children's new information, as a result
        // of potential changes due to recursion down in each subtree
        // Must use the lazy information
        private void pullUp(int node) {
            int l = leftChild(node);
            int r = rightChild(node);

            long leftVal2 = treeMax[l] + lazyMax[l];
            long rightVal2 = treeMax[r] + lazyMax[r];
            treeMax[node] = Math.max(leftVal2, rightVal2);

            long leftVal3 = treeMin[l] + lazyMin[l];
            long rightVal3 = treeMin[r] + lazyMin[r];
            treeMin[node] = Math.min(leftVal3, rightVal3);
        }

        // transfer the lazy information stored at a node down to its children
        private void pushDown(int node) {
            lazyMax[leftChild(node)] += lazyMax[node];
            lazyMax[rightChild(node)] += lazyMax[node];
            lazyMax[node] = 0;

            lazyMin[leftChild(node)] += lazyMin[node];
            lazyMin[rightChild(node)] += lazyMin[node];
            lazyMin[node] = 0;
        }

        // Always begin the updating with the root of the tree
        public void updateRange(int l, int r, int val) {
            updateRangeHelper(1, l, r, val);
        }

        // Update a range [l, r] by val
        // Recursively walk down to our children:
        // Either we are completely covered, disjoint, or partially covered
        // KEY POINT: We don't use a mid to break apart the range,
        // since we need to preserve the information about the range.
        // What we ARE splitting is our node into its children, and
        // we'll individually decide which of those children are useful.
        private void updateRangeHelper(int node, int l, int r, int val) {
            if (r < lo[node] || hi[node] < l) {
                // we are completely disjoint with the goal range
                return;
            }
            else if (l <= lo[node] && hi[node] <= r) {
                // Complete covering, let's be lazy
                lazyMax[node] += val;
                lazyMin[node] += val;
            }
            else {
                // Partial covering, forced to recurse down.
                // We may have lazy values from previous updates, so
                // we must propagate it downward
                pushDown(node);

                // Recurse on children
                updateRangeHelper(leftChild(node), l, r, val);
                updateRangeHelper(rightChild(node), l, r, val);

                // After recursion, we may have pending updates from children
                // affecting this node
                pullUp(node);
            }
        }

        // Query the value along a range [l, r]
        // Where we are currently at a certain node and will
        // recurse downward - either being disjoint, contained, or partially
        // covered.

        public long queryMin(int l, int r) {
            NEUTRAL = (int) 1e9;
            return queryMinHelper(1, l, r);
        }

        private long queryMinHelper(int node, int l, int r) {
            if (r < lo[node] || hi[node] < l) {
                // It's disjoint, so return a value that will not affect our
                // ultimate answer
                return NEUTRAL;
            }
            else if (l <= lo[node] && hi[node] <= r) {
                // We must apply any lazy values that had been placed here earlier
                // min:
                return treeMin[node] + lazyMin[node];
                // sum:
                // todo return tree[node] + (hi[node] - lo[node] + 1) * lazy[node]
            }
            else {
                // First, propagate any pending lazy values
                pushDown(node);

                // Partial covering, so we must recurse
                // and gather information from the depths
                long leftResult = queryMinHelper(leftChild(node), l, r);
                long rightResult = queryMinHelper(rightChild(node), l, r);

                // Technically, this pullUp can be called IMMEDIATELY after
                // pushing down, since the values aren't actually changing,
                // it's just that we lost our lazy value, (and our value no longer
                // reflects the true rangeQuery value that node represents)
                pullUp(node);

                // The lazy values will have been included already
                return Math.min(leftResult, rightResult);
            }
        }

        public long queryMax(int l, int r) {
            NEUTRAL = (int) -1e9;
            return queryMaxHelper(1, l, r);
        }

        private long queryMaxHelper(int node, int l, int r) {
            if (r < lo[node] || hi[node] < l) {
                // It's disjoint, so return a value that will not affect our
                // ultimate answer
                return NEUTRAL;
            }
            else if (l <= lo[node] && hi[node] <= r) {
                // We must apply any lazy values that had been placed here earlier
                // min:
                return treeMax[node] + lazyMax[node];
                // sum:
                // todo return tree[node] + (hi[node] - lo[node] + 1) * lazy[node]
            }
            else {
                // First, propagate any pending lazy values
                pushDown(node);

                // Partial covering, so we must recurse
                // and gather information from the depths
                long leftResult = queryMaxHelper(leftChild(node), l, r);
                long rightResult = queryMaxHelper(rightChild(node), l, r);

                // Technically, this pullUp can be called IMMEDIATELY after
                // pushing down, since the values aren't actually changing,
                // it's just that we lost our lazy value, (and our value no longer
                // reflects the true rangeQuery value that node represents)
                pullUp(node);

                // The lazy values will have been included already
                return Math.max(leftResult, rightResult);
            }
        }

        private int leftChild(int node) {
            return 2 * node;
        }

        private int rightChild(int node) {
            return 2 * node + 1;
        }
    }

    static final class FastScanner {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public FastScanner() {
            this.stream = System.in;
        }

        private int read() throws IOException {
            if (curChar >= numChars) {
                curChar = 0;
                numChars = stream.read(buf);
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public final String readString() throws IOException {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public final String readString(int L) throws IOException {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder(L);
            do {
                res.append((char) c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public final int readInt() throws IOException {
            int c = read();
            boolean neg = false;
            while (isSpaceChar(c)) {
                c = read();
            }
            char d = (char) c;
            // log("d:"+d);
            if (d == '-') {
                neg = true;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            // log("res:"+res);
            if (neg)
                return -res;
            return res;

        }

        public final long readLong() throws IOException {
            int c = read();
            boolean neg = false;
            while (isSpaceChar(c)) {
                c = read();
            }
            char d = (char) c;
            // log("d:"+d);
            if (d == '-') {
                neg = true;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            // log("res:"+res);
            if (neg)
                return -res;
            return res;

        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}