Ashton Carl McDonalds (known as A.C.M.) works at a company called XOR (XptO Revolution). The company has a simple rule for employee identification: each employee must have an integer id that must be unique (no two employees may have the same id).

Recently, the employees were grouped into teams, in the following way: the teams are intervals on the XOR’s employees list. An employee can be part of more than one team.

The company wants to hire new employees, and needs to generate id numbers for them. However, due to a security flaw in Human Resources software, the company can’t assign a new number that, if one executes Exclusive-Or operation with all numbers of any team, results in 0.

McDonalds, as the leader lazy programmer of XOR, needs your help to determine if a given number can or can’t be assigned to a new employee.

Input

The input contains multiple test cases.

The first line of each test case contains three numbers, N, T and Q, the number of employees in the company, the number of teams and the number of new numbers to be queried, respectively.

The second line contains N numbers X_i, 1 <= i <= N, distinct, the employees id numbers.

Each one of the following E lines contains two numbers, A and B, which represent an interval that forms a team. It means that the employees identified by X_A, …, X_B form one team.

Each one of the following Q lines contains one number Y_j, the queried number.

Limits: 1 <= N, T, Q <= 10⁵, 1 <= A <= B <= N. All X_i and Y_j will be non-negative and fit into a signed 32 bit integer, and all queries must be treated as independent from others (just the initial employees and teams must be taken into account).

Output

For each test case, the program must print Q + 1 output lines. For each queried number, the program must print ‘Y’, if the number can be assigned to a new employee, or ‘N’, otherwise. The last line is a simple minus sign ‘-’.

Example

Input:
3 2 4
1 2 4
1 2
1 3
3
5
6
7
0 0 0
Output:
N
Y
Y
N
-