E. Richard Lore
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jinshi loves his toys, and his two favorite toys are an array $$$a$$$ of length $$$n$$$ and a sequence of $$$m$$$ pairs of integers, the $$$i$$$'th being $$$x_i$$$ and $$$y_i$$$ $$$(1 \leq x_i, y_i \leq n)$$$. Whenever Jinshi is bored, he likes to try and sort $$$a$$$ with his $$$m$$$ pairs of integers. Jinshi will loop over the pairs in order from $$$1$$$ to $$$m$$$, and swap $$$a_{x_i}$$$ and $$$a_{y_i}$$$. He will be happy if after all $$$m$$$ swaps, $$$a$$$ becomes sorted in increasing order. Afterward, Jinshi will restore $$$a$$$ to what it was before all the swaps happened.

Maomao will mess with Jinshi over the following $$$q$$$ days, where on the $$$i$$$'th day, she will swap $$$a_{l_i}$$$ and $$$a_{r_i}$$$ $$$(1 \leq l_i, r_i \leq n)$$$. Without knowing Maomao has messed with his array, Jinshi will try to sort it every day after Maomao does the swap. Maomao will not restore $$$a$$$ after doing the swap. On each day, find out if Jinshi will successfully sort his array.

Input

The first line of input contains three integers $$$n \ m \ q$$$ denoting the length of the array, the number of pairs, and the number of days Maomao will mess with Jinshi $$$(1 \leq n, m, q \leq 10^5)$$$.

The following line contains $$$n$$$ spaced integers, the $$$i$$$'th being $$$a_i$$$, denoting Jinshi's array $$$(1 \leq a_i \leq n)$$$.

The following $$$m$$$ lines contain two integers each, the $$$i$$$'th line containing $$$x_i \ y_i$$$ denoting the $$$i$$$'th pair of integers in Jinshi's $$$m$$$ pairs $$$(1 \leq x_i, y_i \leq n)$$$.

The following $$$q$$$ lines contain two integers each, the $$$i$$$'th line containing $$$l_i \ r_i$$$ denoting the pair of elements Maomao swaps on the $$$i$$$'th day $$$(1 \leq l_i, r_i \leq n)$$$.

—

Tests are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

All odd-numbered tests satisfy that $$$a$$$ is a permutation. In other words, all the elements in $$$a$$$ will be unique.

Tests $$$1 - 10$$$ satisfy $$$n, m, q \leq 1000$$$.

The remaining tests do not satisfy any additional constraints.

Output

Output a string of length $$$q$$$, the $$$i$$$'th character being $$$Y$$$ if Jinshi can sort his array on the $$$i$$$'th day or $$$N$$$ otherwise.

Examples
Input
5 3 6
1 4 2 3 5
3 4
1 2
4 1
1 3
1 4
3 4
3 1
3 4
5 5
Output
YNNNYY
Input
5 1 7
1 2 1 2 4
2 3
2 4
1 2
2 3
3 4
4 1
1 2
2 3
Output
YNNNNNY
Note

On the first day, the array becomes $$$[2, 4, 1, 3, 5]$$$ after Maomao swaps $$$a_{1}$$$ and $$$a_{3}$$$. Jinshi will then attempt to sort his array, which changes as follows:

$$$[2, 4, 1, 3, 5] \rightarrow [2, 4, 3, 1, 5] \rightarrow [4, 2, 3, 1, 5] \rightarrow [1, 2, 3, 4, 5]$$$

Since Jinshi's array is sorted, the first character in the output string is $$$Y$$$.

—

Problem Idea: 3366

Problem Preparation: 3366

Occurrences: Novice 5, Advanced 2