You are given an array A of length N weights of masses A_1, A_2...A_N. No two weights have the same mass. You can put every weight on one side of the balance (left or right). You don't have to put weights in order A_1,...,A_N. There is also a string S consisting of characters "L" and "R", meaning that after putting the i-th weight (not A_i, but i-th weight of your choice) left or right side of the balance should be heavier. Find the order of putting the weights on the balance such that rules of string S are satisfied. 

Input

The first line contains one integer N (1 ≤ N ≤ 2*10^5) - the length of the array A The second line contains N distinct integers: A_1, A_2,...,A_N (1 ≤ A_i ≤ 10^9) - the weights given The third line contains string S of length N consisting only of letters "L" and "R" - string determining which side of the balance should be heavier after putting the i-th weight of your choice

Output

The output contains N lines. In every line, you should print one integer and one letter - integer representing the weight you are putting on the balance in that move and the letter representing the side of the balance where you are putting the weight. If there is no solution, print -1.

Example

Input


5
3 8 2 13 7
LLRLL


Output


3 L
2 R
8 R
13 L
7 L

Note

Explanation for the test case: 

after the 1st weight: 3 L (left side is heavier)

after the 2nd weight: 2 R (left side is heavier)

after the 3rd weight: 8 R (right side is heavier)

after the 4th weight: 13 L (left side is heavier)

after the 5th weight: 7 L (left side is heavier)

So, the rules given by string S are fulfilled and our order of putting the weights is correct.
5
3 8 2 13 7
LLRLL

7 L
3 R
8 R
13 L
2 L

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, cnt, a[N], s[N], ans[N], op[N];
char ch[N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  scanf("%s", ch + 1);
  for (int i = 1; i <= n; i++) s[i] = (ch[i] == 'R');
  for (int i = 1; i < n; i++) cnt += (s[i] != s[i + 1]);
  int l = n - cnt, r = n - cnt;
  for (int i = 1; i <= n; i++) {
    if (i == 1) {
      ans[i] = n - cnt;
      op[i] = s[i];
    } else {
      if (s[i] == s[i - 1]) {
        ans[i] = --l;
        op[l] = op[l + 1] ^ 1;
      } else {
        ans[i] = ++r;
        op[r] = s[i + 1];
      }
    }
  }
  for (int i = 1; i <= n; i++)
    printf("%d %c\n", a[ans[i]], (op[ans[i]] ? 'R' : 'L'));
  return 0;
}
