Time Complexity Verification

Little Ming is learning a new programming language A++ and has just mastered loop statements. Excited by his progress, he wrote many programs and provided his own calculated time complexities for each. His programming teacher does not want to check every single program manually – now it is your chance!

The task is to write a program to verify whether the time complexity claimed by Little Ming is correct.

The A++ language loop structure is as follows:

F i x y
    // loop body
E

Here, F i x y creates a new variable i (its name must not conflict with any currently active variable) and initializes it to x. Then, before each iteration, it checks if i ≤ y. If so, the loop body is executed; otherwise, the loop terminates. After each iteration, i is incremented by 1. When the loop ends (an E line is encountered), the variable i is destroyed.

The parameters x and y can be either positive integers or the variable n. Note that n indicates the size of the input and should not be treated as a constant in complexity analysis—it is very large (≫100).

For convenience, the time complexity is described using the notation \(\operatorname O\) (which in this problem represents the same concept as \(\Theta\) in typical complexity analysis). For example, O(n^2) and O(1) are valid complexities.

Each test case consists of a program written in A++ along with a claimed time complexity. Your program must verify whether the claimed complexity is correct.

Analysis:

• The input begins with an integer t indicating the number of test cases.
• For each test case, the first line contains an integer l (the number of lines in the program) and the claimed complexity in the form O(n^k) or O(1) (which means \(k=0\)).
• The next l lines describe the program. A line starting with F is of the form: F i x y, and a line with E marks the end of a loop.

The overall (actual) time complexity is determined by the maximum exponent of n contributed by any active loop path:

• If both x and y are constants and x > y, the loop does not execute.
• If x is a constant and y is n, the loop runs ~n times and contributes 1 to the complexity exponent.
• If x is n and y is a constant, then since \(n\) is extremely large, the loop never executes.
• If both x and y are n, the loop executes exactly once and contributes 0 to the exponent.
• Loops that do not execute (inactive loops) cause the entire branch to be inactive.

Also, if a variable is reused in a nested loop while still active, the program is invalid and should print ERR.

After simulating the program, if no errors are detected, output:

• Yes if the actual maximum exponent matches the claimed complexity
• No otherwise
</p>

inputFormat

The input begins with an integer t, the number of test cases. Each test case is described as follows:

• The first line contains an integer l (the number of lines in the program) and the claimed complexity, e.g. O(n^2) or O(1).
• The following l lines describe the A++ program. Each line is either:
• A loop start in the form: F i x y (where i is the loop variable, and x and y are either a positive integer or n).
• An E line that marks the end of a loop.

Note: There will be no extra spaces and the input adheres strictly to the described format.

outputFormat

For each test case, output a single line:

• If a variable is reused in an active scope, output ERR.
• Otherwise, output Yes if the computed maximum exponent of n equals the exponent in the claimed complexity, or No if it does not.

sample

1
2 O(n)
F i 1 n
E

Yes

</p>