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\le u,v\le 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 5000,M\le 500000,Q\le 100000$), 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 10000$
$2$	$40$	$N\le 3000$, $M\le 50000$
$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