Problem D
Nice Walks

Two of the three required venues. CC BY-SA 4.0 by Rodhullandemu on Wikimedia Commons

Ivan likes going on nice walks. According to Ivan, a nice walk must first of all take the shortest path between two points, since being inefficient is not very nice. However, to be considered truly nice, in Ivan’s opinion, a walk must also allow for sufficient leisure activities along the way. In particular, a nice walk must pass by at least one park, at least one coffee shop, and at least one ice cream parlor (though not necessarily in that order).

Ivan has recently moved to a new city and would like your help identifying some nice walks. In particular, Ivan has marked some potential walks on a map of the city, and needs your help to figure out which ones are nice.

Input

The first line of input contains three space-separated integers $n\; v\; q$, where $n$ represents the number of intersections on the map, $v$ the number of venues, and $q$ the number of queries ($2 \leq n \leq 10^5$, $0 \leq v \leq 10^5$, $1 \leq q \leq 10^5$). The intersections are numbered $1$ through $n$.

The next $n-1$ lines each contain two distinct integers $a$ and $b$ ($1 \leq a, b \leq n$) describing the endpoints of a two-way road connecting intersections $a$ and $b$. It is guaranteed that any location will be reachable from any other by a sequence of roads. The roads are also numbered $1$ through $n-1$ in the order they are listed.

The next $v$ lines describe the venues. Each line contains a letter $x$ followed by an integer $r$ ($1 \leq r \leq n-1$) indicating that a venue of type $x$ is located on road $r$. The letter $x$ will be one of P, C, or I, denoting a park, coffee shop, or ice cream parlor, respectively. Note that a given road may contain multiple venues, even multiple venues of the same type.

Finally, the last $q$ lines each describe a query. A query consists of two integers $s$ and $t$ ($1 \leq s,t \leq n$) denoting the endpoints of a walk.

Output

For each query $s\; t$, output Y or N indicating whether or not the shortest walk from intersection $s$ to intersection $t$ is a nice walk, that is, whether the roads along the shortest path from $s$ to $t$ contain at least one of each type of venue.

3 3 2
1 2
2 3
I 1
P 1
C 2
1 2
3 1

N
Y