Each building in a school has a unique ID. One day, feeling bored, you decide to wander around the campus.

Having spent some time at the school, you are very familiar with the ID of each building. You couldn't help but write down the IDs of the surrounding buildings—but you didn't actually write down the full IDs. Instead, you took the remainder of each building's ID divided by 2 (getting 0 or 1) as the label for that building. The labels of multiple buildings visited in sequence form a 01-string.

You are very interested in this string, especially when it is a palindrome, so you decide to study this problem.

The school can be modeled as an undirected graph, where buildings are vertices and some pairs of vertices are connected by undirected edges. Each vertex has a label (0 or 1). Each time, you will choose two vertices in the graph, and you want to know if there exists a path between these two vertices such that the labels of the vertices along the path form a palindrome.

A palindrome is a string that reads the same backwards as forwards, such as "010" and "1001", while "01" and "110" are not. Note that a string of length 1 is always a palindrome, so if the two queried vertices are the same, such a path always exists. Also, note that the path does not have to be a simple path, meaning that each edge and vertex can be visited any number of times.

Input Format

The first line contains three integers $n, m, q$, representing the number of vertices, the number of edges, and the number of queries, respectively.

The second line contains a 01-string of length $n$, where the $i$-th character represents the label of the $i$-th vertex (i.e., vertex $i$). Vertices are 1-indexed.

Each of the next $m$ lines contains two integers $u_i, v_i$, representing an undirected edge between vertex $u_i$ and vertex $v_i$. There are no self-loops or multiple edges.

Each of the next $q$ lines contains two integers $x_i, y_i$, representing a query asking whether there is a path between vertex $x_i$ and vertex $y_i$ that satisfies the condition.

Output Format

Output $q$ lines, each containing either the string YES or NO. Output YES if a path satisfying the condition exists, and NO otherwise.

Examples

Input 1

5 4 2
00010
4 5
1 3
4 2
2 5
3 5
1 3

Output 1

NO
YES

Note

For the first query, vertex 3 and vertex 5 are not connected, so the answer is NO.

For the second query, a valid path is $1 \to 3$, and the string formed by the labels along the path is "00". Note that the valid path is not unique.

Input 2

10 11 10
0011011111
4 6
10 6
5 9
4 7
10 7
5 8
1 9
5 7
1 10
5 1
5 6
10 3
7 4
8 10
9 4
8 9
6 6
2 2
9 9
10 9
3 4

Output 2

NO
YES
YES
NO
YES
YES
YES
YES
YES
NO

Constraints

• For $30\%$ of the data, $1 \le m \le 10000$.
• For $70\%$ of the data, $1 \le m \le 50000$.
• For $100\%$ of the data, $1 \le n \le 5000$, $1 \le m \le 500000$, $1 \le q \le 100000$.