Mitochondrial Eve

Mitochondrial DNA is a DNA molecule held by the mitochondria inside a living organism's cells.

This DNA is inherited only maternally (through the mother). As a result, all of humanity shares a single common maternal ancestor, the so-called "Mitochondrial Eve." A maternal ancestor is one you reach by climbing a family tree along the female line only: mother, then her mother, and so on. For example, your mother and your maternal grandmother are both maternal ancestors.

Humanity's Mitochondrial Eve is estimated to have lived in East Africa about 200,000 years ago.

This problem concerns a population made up of a single heterozygous eukaryotic species. Researchers recorded every change in the population's size in chronological order and sequenced the mitochondrial DNA of some of the individuals. Assume that within the observed population, mitochondrial DNA is passed down the maternal line without any mutation.

Write a program that determines whether every individual alive at the end of the observation carries the same mitochondrial DNA.

The first line contains an integer $n$ ($1 \le n \le 100000$), the number of individuals alive when the observation began. These individuals have IDs $1$ through $n$.

Each of the next $n$ lines contains a single character. The character on line $i$ is the sex of the individual with ID $i$: M for male and F for female.

The next line contains an integer $m$ ($0 \le m \le 100000$), the total number of birth and death events during the observation period.

Each of the next $m$ lines describes one event, in chronological order.

• A birth is given as three values, in order: the father's ID, the mother's ID, and the newborn's sex (M or F). The newborn's ID is the smallest positive integer that has never been used as an ID so far.
• A death is given as a single negative number: the ID of the individual that died, with a minus sign in front.

The next line contains an integer $k$ ($0 \le k \le n + m$), the number of sequenced mitochondrial DNAs.

Each of the next $k$ lines contains two integers separated by a space. The first is the ID of the individual whose mitochondrial DNA was analyzed, and the second is that DNA's unique identifier. Two DNAs having the same unique identifier is equivalent to the two DNAs being identical. The unique identifier is an integer between $1$ and $10^9$.

All given data is mutually consistent, and each individual's mitochondrial DNA is analyzed at most once. At least one individual is alive at the end of the observation.

Output a single word.

• YES — it is certain that every individual alive at the end of the observation carries the same mitochondrial DNA.
• NO — it is certain that some living individuals carry different mitochondrial DNA from one another.
• POSSIBLY — the given information is not enough to decide between YES and NO.