Cowculations

Time limit1sMemory limit128 MB

Summary

For each tablet, simulate three operations (add, shift right, shift left, or null) on a five-symbol cow number and check the padded result equals the eight-symbol line.

Level: Medium4 of 10
Topics: Implementation, Simulation, String, Array
Solved: No attempts yet

Problem

A primitive cow culture was discovered by the noted anthropologist Dr. Bo Vine. Hundreds of computation tablets were unearthed in a pasture near Dallas. Dr. Vine deciphered them once he realized they represent mathematical calculations. He says, "I've always suspected that cows are smarter than they let on, and here is the proof."

Each tablet has six lines, and each line is a sequence of cow symbols.

Lines 1 and 2: two cow numbers
Lines 3 to 5: operations applied to those numbers
Line 6: the result

Cow numbers use four symbols: V, U, C, and D. The numbers on lines 1 and 2 are always sequences of 5 symbols, and the number on line 6 is always a sequence of 8 symbols.

To interpret a calculation, keep track of two numbers, Num1 and Num2. Initially Num1 equals the number on line 1 and Num2 equals the number on line 2. Num1 never changes, but Num2 can change as a result of the operations. There are four operations: A, R, L, and N.

Operation A replaces Num2 with the "sum" of Num1 and Num2, using this addition table:

 A  | V    U    C    D
-----------------------
 V  | V    U    C    D
 U  | U    C    D   V,U
 C  | C    D   V,U  U,U
 D  | D   V,U  U,U  C,U

In each cell, the first symbol is the sum and the second symbol is the carry. For example, U A V = U, and C A C = V with a carry of U. Examples of cow addition: VUCDV A VUCDV = VDUCV, and DVVCU A CVUCU = UUVCVC.

Operation R shifts the symbols of Num2 one position to the right; the rightmost symbol is lost and a V is placed in the leftmost position. For example, VVCDU becomes VVVCD.

Operation L shifts the symbols of Num2 one position to the left; the leftmost symbol is kept and a V is placed in the rightmost position. For example, VVCDU becomes VVCDUV.

Operation N is the null operation and has no effect on Num2.

After all three operations are applied, the final value of Num2 should equal the value on line 6. If the final Num2 uses fewer than 8 symbols, it is padded on the left with V's (for example, VDCCC becomes VVVVDCCC).

The format of every tablet (number of lines, symbol counts, symbol types) is already known to be valid. Your task is to verify that the result of the calculation described on lines 1 to 5 really is the value on line 6.

Input

The first line contains an integer $N$ ( $1 \le N \le 10$ ), the number of tablets. The next $6 \times N$ lines describe the $N$ tablets in the format above.

Output

For each tablet, print a single line: YES if the tablet follows Dr. Vine's hypothesis, or NO if it does not.

Examples3

Example 1

Input

5
VVVVU
VVVVU
A
A
A
VVVVVVUV
VVCCV
VVDCC
L
R
A
VVVVUCVC
VVCCV
VVDCC
R
L
A
VVVVUCVV
VVUUU
VVVVU
A
N
N
VVVVVUCU
DDDDD
VVVVU
A
L
L
UVVVVVVV

Expected output

YES
YES
YES
NO
YES

Example 2
Input
```
1
VVVUC
VVVUU
A
N
N
VVVVVVCD
```
Expected output
```
YES
```
Example 3
Input
```
1
VUCDV
VUCDV
A
N
N
VVVVDUCV
```
Expected output
```
YES
```