HA_29

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
private:
    vector<vector<int> > adj;
    vector<bool> used;
    vector<vector<int> > matrix;
    int rows, cols;
    int original_value;
    int new_value;

public:
    Graph(int vertex_count, const vector<vector<int> >& input_matrix) {
        adj.resize(vertex_count);
        used.resize(vertex_count, false);
        matrix = input_matrix;
        rows = matrix.size();
        cols = matrix[0].size();
    }

    void add_edge(int from, int to) {
        adj[from].push_back(to);
    }

    void build_graph() {
        int dx[] = { -1, 1, 0, 0 }; // вверх, вниз
        int dy[] = { 0, 0, -1, 1 }; // влево, вправо

        for (int x = 0; x < rows; ++x) {
            for (int y = 0; y < cols; ++y) {
                int from = x * cols + y;
                for (int dir = 0; dir < 4; ++dir) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                        int to = nx * cols + ny;
                        add_edge(from, to);
                    }
                }
            }
        }
    }

    void flood_fill(int x, int y, int new_value) {
        int start_v = x * cols + y;
        this->new_value = new_value;
        original_value = matrix[x][y];
        if (original_value == new_value) {
            return;
        }
        BFS(start_v);
    }

    bool BFS(int start_v) {
        queue<int> q;
        q.push(start_v);
        used[start_v] = true;
        matrix[start_v / cols][start_v % cols] = new_value;

        while (!q.empty()) {
            int cur_v = q.front();
            q.pop();

            for (size_t i = 0; i < adj[cur_v].size(); ++i) {
                int nei = adj[cur_v][i];
                if (!used[nei]) {
                    int nx = nei / cols;
                    int ny = nei % cols;
                    if (matrix[nx][ny] == original_value) {
                        q.push(nei);
                        used[nei] = true;
                        matrix[nx][ny] = new_value;
                    }
                }
            }
        }
        return false;
    }

    void print_matrix() const {
        for (size_t i = 0; i < matrix.size(); ++i) {
            const vector<int>& row = matrix[i];
            for (size_t j = 0; j < row.size(); ++j) {
                cout << row[j];
                if (j < row.size() - 1) {
                    cout << " ";
                }
            }
            cout << endl;
        }
    }
};

int main() {
    vector<vector<int> > matrix;
    string line;
    int start_x = -1, start_y = -1, new_value = -1;

    while (getline(cin, line)) {
        if (line.empty()) {
            continue;
        }

        vector<int> nums;
        size_t pos = 0;

        while (pos < line.size()) {
            // Пропуск пробелов и табуляций
            while (pos < line.size() && (line[pos] == ' ' || line[pos] == '\t')) {
                ++pos;
            }

            // Сборка числа
            int num = 0;
            bool found = false;
            while (pos < line.size() && isdigit(line[pos])) {
                num = num * 10 + (line[pos] - '0');
                ++pos;
                found = true;
            }

            if (found) {
                nums.push_back(num);
            } else {
                ++pos;
            }
        }

        if (nums.empty()) {
            continue;
        }

        if (nums.size() == 3 && start_x == -1) {
            start_x = nums[0] - 1;
            start_y = nums[1] - 1;
            new_value = nums[2];
            break;
        } else {
            matrix.push_back(nums);
        }
    }

    if (start_x == -1 || matrix.empty()) {
        cout << "Некорректный ввод" << endl;
        return 0;
    }

    int vertex_count = matrix.size() * matrix[0].size();
    Graph graph(vertex_count, matrix);
    graph.build_graph();
    graph.flood_fill(start_x, start_y, new_value);
    graph.print_matrix();

    return 0;
}