FRAKTAL - konkurs programistyczny

Romek jest posiadaczem dwóch ciągów liczbowych a oraz b. Każdy z ciągów składa się z n elementów. Każdy element ciągu to cyfra dziesiętna. Każdy element ciągu możemy obrócić czyli zamienić bieżącą cyfrę na następną: 0 → 1, 1 → 2, 2 → 3, 3 → 4, 4 → 5, 5 → 6, 6 → 7, 7 → 8, 8 → 9, 9 → 0.

Nasz bohater twierdzi, że z ciągu a można uzyskać ciąg b wykonując na nim q operacji. Pojedyncza operacja składa się z trzech liczb całkowitych l, r oraz k, oznaczających, że elementy ciągu a od pozycji l do pozycji r powinny zostać obrócone k razy.

Odpowiedz na pytanie, czy twierdzenie Romka jest prawdziwe?

Wejście

W pierwszej linii wejścia znajduje się liczba elementów w każdym z ciągów n ∈ [1, 10⁵] oraz liczba operacji q ∈ [1, 10⁵].

W drugiej linii wejścia znajduje się n cyfr dziesiętnych a₁, a₂, a₃, ..., a_n określających kolejne elementy ciągu a.

W trzeciej linii wejścia znajduje się n cyfr dziesiętnych b₁, b₂, b₃, ..., b_n określających kolejne elementy ciągu b.

W kolejnych q liniach znajdują się operacje. Każda operacja składa się z trzech liczb całkowitych l r k (1 ≤ l ≤ r ≤ n; 1 ≤ k ≤ 10⁹) opisanych powyżej.

Wyjście

Na wyjściu należy wypisać TAK jeżeli twierdzenie Romka jest prawdziwe albo NIE w przeciwnym wypadku.

Przykład 1

Wejście

8 5
2 0 2 2 0 4 2 0
4 4 4 4 4 4 4 4
1 5 2
8 8 2
2 2 2
7 8 2
5 5 2

Wyjście

TAK

Wyjaśnienie do przykładu

Twierdzenie Romka jest prawdziwe. Ciąg a po wykonaniu kolejnych operacji będzie wyglądał następująco:

• 4 2 4 4 2 4 2 0
• 4 2 4 4 2 4 2 2
• 4 4 4 4 2 4 2 2
• 4 4 4 4 2 4 4 4
• 4 4 4 4 4 4 4 4

Pogrubioną czcionką zaznaczone zostały elementy ciągu obrócone w każdej operacji.

Przykład 2

Wejście

2 1
1 9
9 1
1 2 8

Wyjście

NIE

Wyjaśnienie do przykładu

Twierdzenie Romka nie jest prawdziwe. Ciąg a po wykonaniu jedynej operacji będzie wyglądał następująco:

• 9 7