#include <bits/stdc++.h>
using namespace std;

bool match(const string& word, const string& origin) {
	if (word.size() != origin.size())
		return false;
	char wordArr[256];
	memset(wordArr, 0, sizeof(wordArr));
	for (char c : word) {
		++wordArr[c];
	}
	for (char c : origin) {
		--wordArr[c];
	}
	for (int i = 0; i < 256; ++i) {
		if (wordArr[i] != 0)
			return false;
	}
	return true;
}

int main() {
	string origin, rep, sentence;
	getline(cin, origin);			// 不能用cin,cin不会把最后的换行符读出来
	getline(cin, sentence);
	cin >> rep;
	int start = 0, end = 0;
	string res = "";
	while (end < sentence.size()) {
		while (end < sentence.size() && isalpha(sentence[end]))
			++end;
		string cur = sentence.substr(start, end - start);
		if (match(cur, origin))
			res += rep;
		else
			res += cur;
		if (end < sentence.size()) 
			res += sentence[end];
		start = end + 1;
		end = start;
	}
	cout << res << endl;
}

#include <bits/stdc++.h>
using namespace std;

void dfs(const vector<string>& v, vector<string>& res, int index, string path, vector<int>& vis, bool flag) {
	if (index == v.size()) {
		if (flag)
			res.push_back(path + "--circular dependency");
		else
			res.push_back(path);
		return;
	}
	for (int i = 0; i < v[index].size(); ++i) {
		char c = v[index][i];
		++vis[c - 'a'];
		if (vis[c - 'a'] == 1)
			dfs(v, res, index + 1, path + c, vis, flag);
		else
			dfs(v, res, index + 1, path + c, vis, true);
		--vis[c - 'a'];
	}
}

int main() {
	string s;
	vector<string> v;
	while (cin >> s) {
		v.push_back(s);
	}
	vector<string> res;
	vector<int> vis(26, 0);
	dfs(v, res, 0, "", vis, false);
	for (auto s : res) {
		cout << s << endl;
	}
}

#include <bits/stdc++.h>
using namespace std;
int m, n, e, x, l, res;

bool valid(int _x, int _y) {
	return _x >= 0 && _x < m && _y >= 0 && _y < n;
}

void dfs(vector<vector<int>> v, vector<vector<bool>> flag, int cur, int i, int j, int len) {
	if (i == m - 1 && j == n - 1) {
		res = min(res, len);
		return;
	}
	if (i != 0 || j != 0) {
		cur -= v[i][j];
	}
	flag[i][j] = true;		// 设置访问标记

	int dx[4] = {1, -1, 0, 0};
	int dy[4] = {0, 0, 1, -1};

	for (int k = 0; k < 4; ++k) {
		int xx = i + dx[k];
		int yy = j + dy[k];
		// 无效/已访问
		if (!valid(xx, yy) || flag[xx][yy])
			continue;
		// 没有充电次数
		if (x == 0 && cur < v[xx][yy])
			continue;
		// 充了电也没用
		if (l < v[xx][yy])
			continue;
		if (cur < v[xx][yy]) {
			--x;
			dfs(v, flag, l, xx, yy, len + 1);
			++x;
		} else {
			dfs(v, flag, cur, xx, yy, len + 1);
		}
	}
	flag[i][j] = false;		// 取消访问标记
}

int main() {
	// m, n 长宽
	// e: 初始电量
	// x: 充电次数
	// l: 充满多少
	cin >> m >> n >> e >> x >> l;
	// 每格消耗电量
	vector<vector<int>> v(m, vector<int>(n));
	vector<vector<bool>> flag(m, vector<bool>(n, false));	// 访问标记
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> v[i][j];
		}
	}
	res = INT_MAX;
	dfs(v, flag, e, 0, 0, 1);
	if (res != INT_MAX)
		cout << res << endl;	
	else
		cout << "NA" << endl;
}