Archiwum zadań programistycznych WWSI

Widziałeś już najnowszy film Jamesa Camerona - "Avatar"? Wytwórnia wyłożyła na niego 250 milionów dolarów. Chodzą jednak słuchy, że tak naprawdę kosztował dwa razy tyle czyli bagatela pół miliarda dolarów. Zastanawiamy się czy te pieniądze się w ogóle zwrócą. Oczywiście ponieważ nie możemy tego oszacować w rzeczywistości, wymyśliliśmy prostą grę, która ma nam w tym pomóc. Nazwaliśmy ją "Wyszukiwanie pieniędzy". W grze tej mamy bardzo dużą tablicę z pewnymi kwotami pieniędzy podanymi w tysiącach dolarów oraz pewną początkową liczbę naturalną S. W każdym kroku gry wykonujemy następujące kroki:

1. Dzielimy liczbę S przez 2 i wynik dzielenia zapisujemy z powrotem w S. Jeżeli liczba S nie jest podzielna bez reszty przez 2 to wynik zaokrąglamy w dół.
2. W tablicy z kwotami pieniędzy wyszukujemy kwotę równą S. Jeżeli S nie występuje w tablicy to wyszukujemy kwotę większą od S i jednocześnie jak najbardziej do niej zbliżoną. Znalezioną kwotę oznaczmy jako X. Liczbie S przypisujemy wartość X.
3. Sprawdzamy jaki numer porządkowy w tablicy ma kwota X w kolejności niemalejącej. Numer ten dodajemy do wyniku rozgrywki. Zakładamy, że najmniejsza kwota w tablicy ma numer 0.
4. Jeżeli wynik przekracza wartość 500000 lub trafiliśmy na kwotę o numerze porządkowym równym 0 to kończymy grę.

Jeżeli po zakończeniu gry wynik przekracza 500000 to znaczy, że Cameron miał farta ;-)

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna d (1 ≤ d ≤ 1000) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

Każdy zestaw danych składa się z 3 linii. W pierwszej linii znajduje się liczba n (2 ≤ n ≤ 500000) określająca ilość kwot w tablicy. W kolejnej linii znajduje się n kwot oddzielonych pojedynczymi spacjami. W ostatniej linii znajduje się jedna liczba naturalna S (1 ≤ S ≤ 1000001).

Wyjście

Dla każdego zestawu należy w osobnej linii wypisać TAK, jeżeli po zakończeniu gry wynik przekracza 500000 albo NIE w przeciwnym wypadku.

Przykład

Wejście:

1
5
2 5 4 3 1
10

Wyjście:

NIE

Wyjaśnienie przykładu

Jako, że część osób źle zrozumiała zasady naszej gry poniżej prezentujemy przebieg gry przykładowej:

1. Dzielimy S przez 2. Jako, że 10 dzieli się bez reszty to nowa wartość S to 5.
2. Wyszukujemy 5 w tablicy. Jest ono 4 w kolejności niemalejącej, tak więc wynik przyjmuje początkową wartość 4 zaś nowa wartość S to 5.
3. Dzielimy S przez 2. Ponieważ nie jest podzielne bez reszty nowa wartość S to 2.
4. Wyszukujemy 2 w tablicy. Kwota 2 ma numer porządkowy 1. Dodajemy 1 do wyniku otrzymując 5. Nowa wartość S to 2.
5. Dzielimy S przez 2, otrzymujemy 1. Kwota 1 ma zerowy numer w kolejności niemalejącej, tak więc nic nie dodajemy do wyniku.
6. Ponieważ trafiliśmy na najmniejszy element w tablicy to kończymy grę z wynikiem 5. Cameron nie miał szczęścia.