Mutacje [B]
Limit pamięci: 128 MB
Bajtoccy genetycy od dawna badają sekwencje bajtokwasów dwóch
modelowych organizmów:
nicienia Bajtorhabditis elegans i muszki Bajtophila melanogaster.
Aby stwierdzić, w jakim stopniu sekwencja muszki pochodzi od sekwencji nicienia,
chcieliby oni znaleźć jak najwięcej takich samych fragmentów w tych sekwencjach.
Badania utrudnia fakt, że w wyniku ewolucji gatunków w sekwencjach
mogły wystąpić mutacje, polegające na tym, że pewien rodzaj bajtokwasu
z sekwencji mógł przekształcić się w inny.
Rodzaje bajtokwasów oznaczamy liczbami naturalnymi.
Zakładamy, że mutacja dotyczy wszystkich wystąpień danego rodzaju bajtokwasu
we fragmencie sekwencji.
Przykładowo, fragment 2 1 2 mógł w wyniku jednej mutacji przekształcić się
we fragment 6 1 6, 2 5 2 lub 2 2 2,
ale nie we fragment 2 1 6 lub 1 1 2.
Twoim zadaniem jest pomóc genetykom odpowiadać na pytania o to, czy
dany fragment sekwencji muszki mógł powstać z danego fragmentu sekwencji nicienia
w wyniku co najwyżej jednej mutacji.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą ()
oznaczającą długość sekwencji bajtokwasów nicienia.
Drugi wiersz zawiera ciąg liczb całkowitych ()
oznaczających rodzaje kolejnych bajtokwasów wchodzących w skład sekwencji nicienia.
Trzeci wiersz zawiera jedną liczbę całkowitą ()
oznaczającą długość sekwencji bajtokwasów muszki.
Czwarty wiersz zawiera ciąg liczb całkowitych ()
oznaczających rodzaje kolejnych bajtokwasów wchodzących w skład sekwencji muszki.
Piąty wiersz zawiera jedną liczbę całkowitą ()
oznaczającą liczbę zapytań.
Dalej następuje wierszy, z których każdy zawiera trzy liczby całkowite
, oraz
(,
).
Oznaczają one zapytanie o to, czy fragment sekwencji
bajtokwasów muszki mógł powstać z fragmentu sekwencji
bajtokwasów nicienia w wyniku co najwyżej jednej mutacji.
Wyjście
Twój program powinien wypisać na wyjście wierszy;
-ty z nich powinien zawierać jedno słowo TAK lub NIE
oznaczające odpowiedź na -te zapytanie.
Przykład
Dla danych wejściowych:
6
4 3 2 1 2 2
7
3 2 2 6 1 6 2
5
1 1 1
1 1 2
3 4 3
3 4 4
5 2 2
poprawną odpowiedzią jest:
TAK
NIE
TAK
NIE
TAK
Autor zadania: Jakub Łącki.