Problem description

Ken ma dość życia w cieniu Barbie i postanowił wraz pozostałymi Kenami się zbuntować i przejąć władzę w Barbieworldzie. Barbie oczywiście się to nie spodobało i postanowiły odzyskać władzę siłą. Dzięki generał Barbie, mają one do dyspozycji czołg, który jest w stanie wystrzelić pocisk raz na T sekund. Zamierzają podjechać nim pod ratusz, aby zmusić Kenów do oddania władzy. Aby dostać się pod ratusz, czołg musi przejechać całą N metrową ulicę o 2 pasach ruchu. Niestety, Ken zwiadowca dowiedział się o niecnym planie Barbie i postawił razem z pozostałymi Kenami rozłożyć M₁ + M₂ przeszkód na drodze do ratusza, M₁ na pierwszym pasie oraz M₂ na drugim. To nie koniec złych wiadomości. Jako że czołg jest zabawkowy, to wjechanie w przeszkodę spowoduje jego zniszczenie. Nie byłoby to problemem, gdyby nie fakt, że ze względu na małą dostępną ilość paliwa czołg nie może zostać zatrzymany dopóki nie dojedzie do ratusza. Czołg ten nie może też poruszać się na skos.

Widzimy zatem, że sytuacja nie jest najlepsza, spróbujmy sformalizować nasz problem. Czołg znajduje się we współrzędnych (0,1). Mamy dostępne 2 pasy ruchu. Na pierwszym pasie znajduje się M₁ przeszkód, a na drugim M₂. Celem Barbie jest dostać się do (N+1,1) lub (N+1,2). W każdej możemy (ale nie musimy) zmienić pas ruchu (o ile jest to możliwe) lub/i wystrzelić pocisk zakładając, że minęło T sekund od startu misji oraz ostatni pocisk został wystrzelony co najmniej T sekund wcześniej (lub jeszcze nie został wystrzelony). Operacje te nie muszą być wykonywane koniecznie w tej kolejności. Wystrzelony pocisk leci wzdłuż aktualnego pasa ruchu i niszczy pierwszą napotkaną przed sobą przeszkodę (o ile taka istnieje). Następnie czołg porusza się z (x,y) do (x+1,y). Najechanie na przeszkodę jest równoznaczne z destrukcją czołgu i niepowodzeniem misji.

Czy pomożesz Barbie ustalić plan przejazdu czołgu albo stwierdzisz, że dotarcie do ratusza jest niemożliwe?

Wejście

W pierwszym wierszu wejścia znajdują się 4 liczby całkowite N, M₁, M₂, T opisujące kolejno, długość drogi do ratusza, liczbę przeszkód na pierwszym pasie ruchu, liczbę przeszkód na drugim pasie oraz czas potrzebny do przeładowania. W drugim wierszu wejścia znajduje się M₁ liczb całkowitych X_i, 1 opisujących pozycje przeszkód na pierwszym pasie ruchu. W trzecim wierszu wejścia znajduje się M₂ liczb całkowitych X_i, 2 opisujących pozycje przeszkód na pierwszym pasie ruchu. Zarówno X_i, 1, jak i X_i, 2 są podane rosnąco.

Wyjście

W pierwszym wierszu wyjścia powinno znaleźć się słowo TAK lub NIE w zależności od tego czy czołg może w całości dojechać pod ratusz. Jeżeli zostało wydrukowane TAK to należy w następnych wierszach wypisać opis przejazdu czołgu przez ulicę. W pierszym wierszu opisu należy wypisać liczbę naturalną C₁ opisującą liczbę zmian pasa ruchu. W następnym wierszu należy wypisać C₁ liczb całkowitych p_i(0≤p_i≤N+1) opisujących współrzędną x w których były wykonywane zmiany pasa ruchu. Liczby te mogą być wypisane w dowolnej kolejności. W następnym wierszu należy wypisać liczbę naturalną C₂ opisującą liczbę wystrzałów. W kolejnych C₂ wierszach należy wypisać pary liczb całkowitych sx_i, sy_i opisujące pozycje wystrzałów. Pary te można wypisać w dowolnej kolejności. Suma C₁ + C₂ nie może przekroczyć 2 ⋅ 10⁶. Gwarantowane jest, że jest to zawsze możliwe, jeżeli czołg może się dostać do ratusza. Jeżeli powyższych ciągów operacji jest wiele to wypisz dowolny z nich.

Uwagi

Za poprawne stwierdzenie czy czołg może się przedostać przez ulicę, ale niepoprawny opis przejazdu czołgu, za dany test otrzymuje się 40% punktów.

Ograniczenia

1 ≤ N ≤ 10⁹, 0 ≤ M₁, M₂ ≤ N, 1 ≤ M₁ + M₂ ≤ 10⁶, 1 ≤ T ≤ N, 1 ≤ X_i, j ≤ N.

Podzadania

Przykład

6 2 3 2
2 6
3 5 6

TAK
2
0 3 
2
2 2
4 1

1 1 1 1
1
1

NIE

9 5 2 5
1 2 7 8 9
4 6

TAK
4
0 3 5 10 
1
5 2