Runda 2: Planowanie potopu

Zło szerzy się w Bajtocji: król nie dba o losy kraju, mafia terroryzuje stolicę, policja jest skorumpowana, dorośli nieodpowiedzialni, a dzieci nie chodzą do szkoły. Jedyną szansą dla pogrążonej w chaosie Bajtocji jest odrodzenie w wodach oczyszczającego potopu. Potop, który trzeba jednak najpierw dokładnie zaplanować.

Bajtocja ma kształt prostokąta, który dla wygody dzielimy na w kolumn, po h pól w każdej. Dla każdego pola określona jest jego wysokość nad poziomem morza. Jest pewne szczególne pole, źródło wszelkiego zła, na które spuścimy ulewę. Deszcz będzie padał tylko tam, jednak na szczęście woda, której użyjemy do potopu, rozlewa się oraz ścieka w dół. Dlatego nawet deszcz padający tylko w jednym miejscu po odpowienio długim czasie zawsze zaleje całą Bajtocję. Aby odnieść zamierzony skutek chcemy zalać conajmniej k pól. Jednak z drugiej strony mamy dobre serce i chcemy zalać jak najmniej pól (ale zawsze co najmniej k). Twoim zadaniem jest wyznaczenie obszaru, który należy zalać.

Wejście

W pierwszej linii wejścia dane są liczby w, h, x₀, y₀, k (1 ≤ w, h ≤ 1000, 1 ≤ x₀ ≤ w, 1 ≤ y₀ ≤ h, 1 ≤ k ≤ w * h), oznaczające odpowiednio - ilość kolumn i wierszy mapy, pozycję źródła wszelkiego zła oraz minimalną liczbę pól, którą chcemy zalać. Następnie dana jest mapa w postaci h linii, z których każda zawiera w dodatnich liczb całkowitych nie większych od 10⁶ - są to wysokości pól.

Wyjście

Na wyjściu należy wypisać h linii po w znaków każda, tworzących mapkę Bajtocję po powodzi. Zalane pola należy oznaczyć znakiem x, a suche pola znakiem . (kropka).

Przykład

Źródło wszelkiego zła wyróżniono kolorem niebieskim, a (przykładowe) pasmo górskie wyróżniono kolorem czerwonym. Spuszczając ulewę na źrodło wszelkiego zła możemy zalać dziewięć pól nie przekraczając pasma górskiego (przykład drugi). Aby zalać dziesiąte pole, musimy zalać również jakieś pole z pasma górskiego, co prowadzi jednak do zalania całej Bajtocji - cóż (przykład pierwszy).

Dane 1:
9 5  5 3  10
4 5 6 7 7 7 6 5 4
2 4 7 7 3 7 7 4 2
1 7 7 1 1 1 7 7 1
4 7 2 1 2 1 2 7 4
1 7 7 7 7 7 7 7 1
Odpowiedź 1:
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx

Dane 2:
9 5  5 3  9
4 5 6 7 7 7 6 5 4
2 4 7 7 3 7 7 4 2
1 7 7 1 1 1 7 7 1
4 7 2 1 2 1 2 7 4
1 7 7 7 7 7 7 7 1
Odpowiedź 2:
.........
....x....
...xxx...
..xxxxx..
.........