Problem: There are n lanterns in a row. The lantern i is placed in position i and has power equal to p_i.

Each lantern can be directed to illuminate either some lanterns to the left or some lanterns to the right. If the i-th lantern is turned to the left, it illuminates all such lanterns j that j ∈ [i - p_i, i - 1]. Similarly, if it is turned to the right, it illuminates all such lanterns j that j ∈ [i + 1, i + p_i].

Your goal is to choose a direction for each lantern so each lantern is illuminated by at least one other lantern, or report that it is impossible.

Input

The first line contains one integer t (1 ≤ t ≤ 10000) — the number of test cases.

Each test case consists of two lines. The first line contains one integer n (2 ≤ n ≤ 3 ⋅ 10^5) — the number of lanterns.

The second line contains n integers p_1, p_2, ..., p_n (0 ≤ p_i ≤ n) — the power of the i-th lantern.

The sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, print the answer as follows:

If it is possible to direct all lanterns so that each lantern is illuminated, print YES in the first line and a string of n characters L and/or R (the i-th character is L if the i-th lantern is turned to the left, otherwise this character is R) in the second line. If there are multiple answers, you may print any of them.

If there is no answer, simply print NO for that test case.

Example

Input


4
8
0 0 3 1 1 1 1 2
2
1 1
2
2 2
2
0 1


Output


YES
RRLLLLRL
YES
RL
YES
RL
NO

Solution (in JAVA):

Solution:
/**
 * author: derrick20
 * created: 1/31/21 10:14 PM
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class LanternsRedo {
    static FastScanner sc = new FastScanner();
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) {
//        generate();
        int T = sc.nextInt();
        cases: while (T-->0) {
            int N = sc.nextInt();
            int[] power = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                power[i] = sc.nextInt();
            }
            int[] reach = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                reach[i] = min(N, i + power[i]);
            }
            RMQ reachRMQ = new RMQ(reach);
            int[] farthest = new int[N + 1];
            boolean[] isLeft = new boolean[N + 1];
            int[] end = new int[N + 1]; // If i is L, everything in [end, i - 1] can be R
            Arrays.fill(end, N);
            for (int i = 1; i <= N; i++) {
                int right = 0;
                if (farthest[i - 1] >= i) {
                    right = reach[i];
                }
                int needCovered = max(0, i - power[i] - 1);
                int lower = 0;
                int upper = i - 1;
                while (lower < upper) {
                    int mid = (lower + upper) / 2;
                    if (farthest[mid] >= needCovered) {
                        upper = mid;
                    } else {
                        lower = mid + 1;
                    }
                }
                int left = 0;
                if (farthest[lower] >= needCovered) {
                    int boosted = reachRMQ.query(lower + 1, i - 1);
                    left = max(boosted, i - 1);
//                    System.out.println("At i = " + i + " left = " + left + " vs right = " + right);
                    if (left > max(farthest[i - 1], right)) {
                        /*
                        KEY BUG: it's pretty tricky to say when to be left. The strongest condition is
                        if this move is absolutely optimal relative to the others. Otherwise, we should
                        leave it as an R and then move downward (some of the things we cover might
                        be optimal as an L, so we don't want to miss those)
                         */
                        // if left, right < farthest[i - 1], they're irrelevant
                        isLeft[i] = true;
                        end[i] = lower + 1;
//                        System.out.println(" left goes to " + (lower + 1));
                    }
                }
                farthest[i] = max(farthest[i - 1], max(left, right));
            }
//            System.out.println(Arrays.toString(farthest));
            if (farthest[N] == N) {
                out.println("YES");
                char[] ans = new char[N + 1];
                Arrays.fill(ans, 'R');
                for (int i = N; i >= 1;) {
                    if (isLeft[i]) {
                        ans[i] = 'L';
                        i = end[i] - 1;
                    } else {
                        i--;
                    }
                }
                out.println(new String(ans).substring(1));
                int[] cnt = new int[N + 2];
                for (int j = 1; j <= N; j++) {
                    if (ans[j] == 'L') {
                        cnt[max(1, j - power[j])]++;
                        cnt[j]--;
                    } else {
                        cnt[j + 1]++;
                        cnt[min(N + 1, j + power[j] + 1)]--;
                    }
                }
                boolean noneZero = true;
                for (int j = 1; j <= N; j++) {
                    cnt[j] += cnt[j - 1];
                    noneZero &= cnt[j] > 0;
                }
//                System.out.println(Arrays.toString(farthest));
//                System.out.println(Arrays.toString(cnt));
                if (!noneZero) {
                    System.out.println(Arrays.toString(power));
                }
            } else {
                out.println("NO");
            }
        }
        out.close();
    }

    static void generate() {
        int T = 10;
        System.out.println(T);
        for (int c = 1; c <= T; c++) {
            int N = (int) (80);
            System.out.println(N);
            for (int i = 1; i <= N; i++) {
                System.out.print((int) (random() * N / 10) + " ");
            }
            System.out.println();
        }
    }

    static class RMQ {
        int[][] table;
        int IDENTITY = 0;
        public RMQ(int[] a) {
            int k = -1;
            while ((1 << (k + 1)) <= a.length) {
                k++;
            }
            table = new int[k + 1][a.length];
            for (int i = 0; i < a.length; i++) {
                table[0][i] = a[i];
            }
            for (int p = 1; p <= k; p++) {
                int len = 1 << (p - 1);
                for (int i = 0; i < a.length; i++) {
                    table[p][i] = max(table[p - 1][i], table[p - 1][min(a.length - 1, i + len)]);
                }
            }
        }

        public int query(int i, int j) {
            if (i > j) {
                return IDENTITY;
            }
            int len = j - i + 1;
            int k = -1;
            while ((1 << (k + 1)) <= len) {
                k++;
            }
            return max(table[k][i], table[k][j - (1 << k) + 1]);
        }
    }
    
    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;
    
        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }
    
        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }
    
        char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }
    
        int nextInt() {
            return (int) nextLong();
        }
    
        long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }
    
        double nextDouble() {
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            double cur = nextLong();
            if (c != '.') {
                return neg ? -cur : cur;
            } else {
                double frac = nextLong() / cnt;
                return neg ? -cur - frac : cur + frac;
            }
        }
    
        String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}