Problem description

Back
Show PDF
Znaki ostrzegawcze
(E)
Limit pamięci: 64 MB
Limit czasu: 2.00 s

Karol znowu przemieścił się między kontynentami i tym razem zatrudnił się przy budowie słynnej Drogi Panamerykańskiej.

Zadaniem Karola jest ustawienie znaków ostrzegawczych przed niebezpieczeństwami na jednej z jednokierunkowych jezdni tej drogi zgodnie z poniższymi regułami:

  • Każdy znak musi być przykręcony do słupa. Słupy zostały już wbite w ziemię i Karol wie dokładnie w jakich miejscach drogi.
  • Na każdym słupie mogą być co najwyżej trzy znaki.
  • Każde niebezpieczeństwo na drodze wymaga postawienia znaku co najmniej A i co najwyżej B metrów przed.
  • Każdy znak może informować o tylko jednym niebezpieczeństwie.

Pomóż Karolowi ustawić znaki lub stwierdź, że takie ustawienie nie istnieje.

Napisz program, który wczyta pozycje niebezpieczeństw i słupów, wyznaczy odpowiednie przypisanie znaków do słupów lub rozstrzygnie, że takie nie istnieje i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite N i M oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę niebezpieczeństw i liczbę słupów wbitych przy drodze.

W drugim wierszu wejścia znajdują się dwie dodatnie liczby całkowite A i B oddzielone pojedynczym odstępem i oznaczające odpowiednio minimalną i maksymalną odległość od znaku do niebezpieczeństwa.

W trzecim wierszu wejścia znajduje się N dodatnich liczb całkowitych D1, D2, …, DN pooddzielanych pojedynczymi odstępami i oznaczających odległości (w metrach) kolejnych niebezpieczeństw od początku drogi.

W czwartym wierszu wejścia znajduje się M dodatnich liczb całkowitych S1, S2, …, SM pooddzielanych pojedynczymi odstępami i oznaczających odległości (w metrach) kolejnych słupów od początku drogi.

Wyjście

W pierwszym wierszu wyjścia powinno znaleźć się słowo TAK lub NIE, w zależności od tego czy istnieje rozwiązanie.

Jeśli rozwiązanie istnieje, należy wypisać N kolejnych wierszy. W i-tym z nich powinna znaleźć się jedna dodatnia liczba całkowita oznaczająca numer słupa, na którym został umieszczony znak odpowiadający i-temu z kolei niebezpieczeństwu.

Uwaga: dla niektórych zestawów testowych więcej niż jedna odpowiedź jest poprawna.

Ograniczenia

1 ≤ N, M ≤ 100 000, 1 ≤ A ≤ B ≤ 109, 1 ≤ D1 ≤ D2 ≤ ⋯ ≤ DN ≤ 109, 1 ≤ S1 < S2 < ⋯ < SM ≤ 109.

Przykład

Wejście Wyjście Wyjaśnienie 
3 2
10 20
50 55 70
40 60

TAK
1
1
2

Znaki informujące o pierwszym i drugim niebezpieczeństwie należy postawić na pierwszym słupie, a znak informujący o trzecim niebezpieczeństwie należy postawić na drugim słupie.
Wejście Wyjście Wyjaśnienie 
4 3
15 30
10 20 40 80
5 35 85

NIE

Rozwiązanie nie istnieje, ponieważ w zasięgu czwartego niebezpieczeństwa nie ma żadnego słupa, na którym mógłby być znak.
Wejście Wyjście Wyjaśnienie 
6 2
100 200
300 310 320 330 340 350
100 200

NIE

Rozwiązanie nie istnieje, ponieważ na pierwszym słupie można postawić tylko znak dotyczący pierwszego niebezpieczeństwa, więc pozostałe pięć znaków nie zmieści się na drugim słupie.