Układanie patyków

Limit pamięci: 128 MB

Późno jest, więc będzie bez bajki.

Dany jest ciąg patyków o całkowitych długościach , ustalona liczba oraz zapytań. Każde zapytanie to para liczb całkowitych , , które wyznaczają spójny przedział patyków . Twoim zadaniem jest stwierdzić, czy z każdych patyków z tego przedziału da się ułożyć niezdegenerowany wypukły wielokąt o bokach.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite , (, ). W drugim wierszu znajduje się liczb całkowitych dodatnich () oznaczających długości kolejnych patyków. W trzecim wierszu znajduje się jedna liczba całkowita () oznaczająca liczbę zapytań. W każdym z kolejnych wierszy znajdują się dwie liczby całkowite oznaczające początek i koniec przedziału z zapytania ().

Wyjście

Na wyjście należy wypisać wierszy; w -tym z nich ma znaleźć się słowo TAK, jeżeli z dowolnych patyków o numerach z przedziału da się ułożyć niezdegenerowany wypukły -kąt, lub słowo NIE w przeciwnym wypadku.

Przykład

Dla danych wejściowych:

5 3
10 10 10 10 100
2
1 4
3 5

poprawną odpowiedzią jest:

TAK
NIE

Autor zadania: Wojciech Nadara.