Problem description


Barbieworld
(barbieworld)
Limit pamięci: 256 MB
Limit czasu: 4.00 s

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ć M1 + M2 przeszkód na drodze do ratusza, M1 na pierwszym pasie oraz M2 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ę M1 przeszkód, a na drugim M2. 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, M1, M2, 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ę M1 liczb całkowitych Xi, 1 opisujących pozycje przeszkód na pierwszym pasie ruchu. W trzecim wierszu wejścia znajduje się M2 liczb całkowitych Xi, 2 opisujących pozycje przeszkód na pierwszym pasie ruchu. Zarówno Xi, 1, jak i Xi, 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ą C1 opisującą liczbę zmian pasa ruchu. W następnym wierszu należy wypisać C1 liczb całkowitych pi(0≤piN+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ą C2 opisującą liczbę wystrzałów. W kolejnych C2 wierszach należy wypisać pary liczb całkowitych sxi, syi opisujące pozycje wystrzałów. Pary te można wypisać w dowolnej kolejności. Suma C1 + C2 nie może przekroczyć 2 ⋅ 106. 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 ≤ 109, 0 ≤ M1, M2 ≤ N, 1 ≤ M1 + M2 ≤ 106, 1 ≤ T ≤ N, 1 ≤ Xi, j ≤ N.

Podzadania

Podzadanie Warunki Punkty
1 jeżeli istnieje przeszkoda w (x,y) to istnieje też w (x,3−y) 5
2 M1 + M2, N ≤ 3000 20
3 Brak dodatkowych ograniczeń 75

Przykład

Wejście Wyjście
6 2 3 2
2 6
3 5 6

TAK
2
0 3 
2
2 2
4 1

Wejście Wyjście
1 1 1 1
1
1
NIE
Wejście Wyjście
9 5 2 5
1 2 7 8 9
4 6
TAK
4
0 3 5 10 
1
5 2