## Foxic Expressions

View as PDF

Points: 15
Time limit: 9.0s
Memory limit: 64M

Author:
Problem types
##### University of Toronto ACM-ICPC Tryouts 2012

Let's talk about some definitions, shall we?

An uppercase letter is a character between A and Z, inclusive. You knew that.

A string is a sequence of characters. You probably knew that.

A Foxic letter is a superior uppercase letter - namely, one of F, O, or X. You probably didn't know that.

A Foxic string is a superior string, consisting only of Foxic letters. You didn't know that.

Finally, a Foxic expression is a special string, with each of its characters being either a Foxic letter, or an n immediately following a Foxic letter. A Foxic expression can be translated into a Foxic string by a three-step process. First, up to one character can be added, removed, or modified, provided that the resulting string is still a valid Foxic expression. Next, every Foxic letter immediately preceding an n is replaced by zero or more occurrences of that same letter. Finally, each n is removed. You most certainly did not know that.

There are scenarios to consider, as described above. In each scenario, given a Foxic string of length and a Foxic expression of length , you'd like to determine whether or not can be translated into .

#### Input Specification

Line 1: 1 integer,
For each scenario:
Line 1: 1 integer,
Line 2: 1 string,
Line 3: 1 integer,
Line 4: 1 string,

#### Output Specification

For each scenario:
Line 1: Yes if can be translated into , or No otherwise.

#### Sample Input

2
5
OOOFO
7
OXnFOXn
3
FOX
7
OFnOXnO

#### Sample Output

Yes
No

#### Explanation of Sample

In the first scenario, one possible course of action is to erase the second character of , leaving the Foxic expression OnFOXn. Next, we may choose to replace the first O with three copies of O, and the remaining X with zero occurrences of X, since each of these precedes an n - this yields the string OOOnFOn. Finally, after removing each n, we are left with OOOFO, which matches . Replacing the second character with an O would have also been possible.

In the second scenario, it is impossible to translate into through any valid steps.