Guitar Hero

문제

I PO-juryns 100% originella spel String Instrument Champion visas noter i en låt som punkter på en gitarrs strängar. Noterna representeras som heltal, där heltalet representerar tonhöjden hos noten. Inga två noter spelas samtidigt i någon av String Instrument Champion's låtar.

En låt kan innehålla många fler noter än det finns strängar på gitarren. Därför placerar vi ut noterna på stängarna enligt en viss uppsättning regler. Det går bra ibland, men inte alltid. När vi placerar ut noterna på strängarna har vi följande krav:

• Den första noten får vara på valfri sträng.
• Om den senaste noten hade lägre tonhöjd än nästa not, så måste nästa not vara på en högre sträng.
• Om den senaste noten hade högre tonhöjd än nästa not, så måste nästa not vara på en lägre sträng.
• Om den senaste noten hade samma tonhöjd som nästa not, så måste nästa not vara på samma sträng.

Du får en låt med $nn$ 1-indexerade toner, och gitarren har $mm$ strängar. Du får också $qq$ intervall i låten. Ett intervall representeras av heltalen $aa$ och $bb$, där första noten i intervallet har index $aa$ och sista noten index $bb$.

För varje intervall undrar vi nu: är det möjligt att placera ut de noter som är med i intervallet på strängar så att kraven är uppfyllda?

입력

Den första raden innehåller tre heltal $nn$, $mm$ och $qq$ ($1\le n,m,q\le {10}^{5}1\; \backslash leq\; n,\; m,\; q\; \backslash leq\; 10^5$). Den andra raden innehåller $nn$ heltal $t_{i}t\_i$ ($1\le t_i\le {10}^{9}1\; \backslash leq\; t\_i\; \backslash leq\; 10^9$). Sen följer $qq$ rader med två heltal $a_{i}a\_i$ och $b_{i}b\_i$ vardera ($1\le a_i\le b_i\le n1\; \backslash leq\; a\_i\; \backslash leq\; b\_i\; \backslash leq\; n$).

출력

Du ska skriva ut $qq$ rader med "ja" eller "nej", en för varje intervall. Raden ska innehålla "ja" om det är möjligt att placera ut noterna i intervallet $a_{i}a\_i$ till $b_{i}b\_i$ så att kraven är uppfyllda, annars "nej".

7 3 6
4 1 2 2 3 4 1
1 7
2 6
2 5
3 3
1 5
6 7

nej
nej
ja
ja
ja
ja