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.     (())  
     ^
import java.util.*;
import java.io.*;

public class CFA {
  BufferedReader br;
  PrintWriter out;
  StringTokenizer st;
  boolean eof;
  private static final long MOD = 1000L * 1000L * 1000L + 7;
  private static final int[] dx = {0, -1, 0, 1};
  private static final int[] dy = {1, 0, -1, 0};
  private static final String yes = "Yes";
  private static final String no = "No";

  void solve() {
//    int T = nextInt();
    int T = 1;
    for (int i = 0; i < T; i++) {
      helper();
    }
  }

  void helper() {
    int n = nextInt();
    char[] command = nextString().toCharArray();
    int pointer = 0;
    int LIMIT = 1000 * 1000 + 10;
    int[] arr = new int[LIMIT];
    SegmentMaxLazy seg = new SegmentMaxLazy(arr);
    int prev = 0;
    char[] chars = new char[n];
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < command.length; i++) {
      if (command[i] == 'R') {
        pointer++;
        res.add(prev);
      } else if (command[i] == 'L') {
        pointer = Math.max(0, pointer - 1);
        res.add(prev);
      }
      else {
        int prevCnt = findVal(chars[pointer]);
        int curCnt = 0;
        if (command[i] == '(') {
          curCnt = 1;
        } else if (command[i] == ')') {
          curCnt = -1;
        }
        chars[pointer] = command[i];
        int diff = curCnt - prevCnt;
        if (diff == 0) {
          res.add(prev);
        } else {
          // [pointer, LIMIT - 1] -> + diff.
          seg.update_tree(1, 0, LIMIT - 1, pointer, LIMIT - 1, diff);
          int max = seg.query_max_tree(1, 0, LIMIT - 1, 0, LIMIT - 1);
          int min = seg.query_min_tree(1, 0, LIMIT - 1, 0, LIMIT - 1);
          int sum = seg.query_min_tree(1, 0, LIMIT - 1, LIMIT - 1, LIMIT - 1);
          prev = min != 0 || sum != 0 ? -1 : max;
          res.add(prev);
        }
      }
    }

    for (int v : res) {
      out(v + " ");
    }
  }

  int findVal(char c) {
    if (c == '(') {
      return 1;
    } else if (c == ')') {
      return -1;
    } else {
      return 0;
    }
  }

  public class SegmentMaxLazy {
    int arr[];
    int maxTree[];
    int minTree[];
    int lazy[];
    public SegmentMaxLazy(int[] elements) {
      arr = Arrays.copyOf(elements, elements.length);
      maxTree = new int[4 * arr.length];
      minTree = new int[4 * arr.length];
      lazy = new int[4 * arr.length];
    }

    void build_tree(int node, int nodeStartIndex, int nodeEndIndex) {
      if(nodeStartIndex > nodeEndIndex) return; // Out of range
      if(nodeStartIndex == nodeEndIndex) { // Leaf node
        maxTree[node] = arr[nodeStartIndex]; // Init value
        minTree[node] = arr[nodeStartIndex];
        return;
      }

      build_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2); // Init left child
      build_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex); // Init right child
      maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]); // Init root value
      minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]); // Init root value
    }

    /**
     * Increment elements within range [queryStartIndex, queryEndIndex] with value
     */
    void update_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex, int value) {
      if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) // Current segment is not within range [i, j]
        return;
      if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) { // Segment is fully within range
        maxTree[node] += value;
        minTree[node] += value;
        lazy[node] += value;
        return;
      }

      //-------------
      shift(node, nodeStartIndex, nodeEndIndex);
      //-------------
      update_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex, value); // Updating left child
      update_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex, value); // Updating right child

      maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]); // Updating root
      minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]); // Updating root
    }

    /**
     * Query tree to get max element value within range [queryStartIndex, queryEndIndex]
     */
    int query_max_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
      if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex)
        return Integer.MIN_VALUE; // Out of range
      if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) // Current segment is totally within range [i, j]
        return maxTree[node];

      //-------------
      shift(node, nodeStartIndex, nodeEndIndex);
      //-------------
      int q1 = query_max_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Query left child
      int q2 = query_max_tree(1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Query right child

      return Math.max(q1, q2);
    }
    int query_min_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
      if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex)
        return Integer.MAX_VALUE; // Out of range
      if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) // Current segment is totally within range [i, j]
        return minTree[node];

      //-------------
      shift(node, nodeStartIndex, nodeEndIndex);
      //-------------
      int q1 = query_min_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Query left child
      int q2 = query_min_tree(1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Query right child
      return Math.min(q1, q2);
    }

    private void shift(int node, int nodeStartIndex, int nodeEndIndex) {
      if(lazy[node] != 0) { // This node needs to be updated
        if (nodeEndIndex > nodeStartIndex) {
          maxTree[2 * node] += lazy[node];
          maxTree[2 * node + 1] += lazy[node];
          minTree[2 * node] += lazy[node];
          minTree[2 * node + 1] += lazy[node];

          lazy[node * 2] += lazy[node]; // Mark child as lazy
          lazy[node * 2 + 1] += lazy[node]; // Mark child as lazy
          lazy[node] = 0; // Reset it
        }
      }
    }
  }

  void shuffle(int[] a) {
    int n = a.length;
    for(int i = 0; i < n; i++) {
      int r = i + (int) (Math.random() * (n - i));
      int tmp = a[i];
      a[i] = a[r];
      a[r] = tmp;
    }
  }

  int gcd(int a, int b) {
    while(a != 0 && b != 0) {
      int c = b;
      b = a % b;
      a = c;
    }
    return a + b;
  }
  private void outln(Object o) {
    out.println(o);
  }
  private void out(Object o) {
    out.print(o);
  }
  private void formatPrint(double val) {
    outln(String.format("%.9f", val));
  }
  public CFA() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);
    solve();
    out.close();
  }
  public static void main(String[] args) {
    new CFA();
  }

  public long[] nextLongArr(int n) {
    long[] res = new long[n];
    for(int i = 0; i < n; i++)
      res[i] = nextLong();
    return res;
  }
  public int[] nextIntArr(int n) {
    int[] res = new int[n];
    for(int i = 0; i < n; i++)
      res[i] = nextInt();
    return res;
  }
  public String nextToken() {
    while (st == null || !st.hasMoreTokens()) {
      try {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) {
        eof = true;
        return null;
      }
    }
    return st.nextToken();
  }
  public String nextString() {
    try {
      return br.readLine();
    } catch (IOException e) {
      eof = true;
      return null;
    }
  }
  public int nextInt() {
    return Integer.parseInt(nextToken());
  }
  public long nextLong() {
    return Long.parseLong(nextToken());
  }
  public double nextDouble() {
    return Double.parseDouble(nextToken());
  }
}