Andrew and William are playing a game on an undirected graph with ~N~ vertices, numbered from 1 to ~N~. Each vertex has a binary label, either 0 or 1. During the game, Andrew selects two vertices ~u~ and ~v~ (~1 \leq u, v \leq N~), and asks William if there exists a palindrome path from ~u~ to ~v~. A palindrome path is defined as a path where the sequence of vertex labels recorded from ~u~ to ~v~ forms a palindrome. The path does not have to be a simple path; William can visit the same vertex multiple times.

Write a program to help William determine if such a palindrome path exists for each query.

Input Specification

The first line includes three integers, ~N~, ~M~ and ~Q~ (~N \le 5\,000, M\le 500\,000, Q\le 100\,000~), the number of vertices, the number of edges and the number of queries made by Andrew.

The second line includes a binary string with length ~N~, where the ~i^{th}~ character is the label of vertex ~i~.

Each of the following ~M~ lines includes two integers, ~u~ and ~v~, an edge between ~u~ and ~v~.

Each of the following ~Q~ lines includes two integers, ~u~ and ~v~, a query to ask if there exists a palindrome path from ~u~ to ~v~.

Output Specification

For each query, print out YES if there exists a palindrome path, otherwise NO.

Constraints

Subtask	Points	Additional constraints
~1~	~30~	~M \le 10\,000~
~2~	~40~	~N \le 3\,000~, ~M \le 50\,000~
~3~	~30~	No additional constraints

Sample Input

5 4 2
11101
4 5
1 3
4 2
2 5
1 5
1 3

Sample Output

NO
YES