Given a string S on which you need to perform Q replace operations.
Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.
Note:  All these operations occur simultaneously. It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0,1], sources = ["ab", "bc"] is not a valid test case. 
Example 1:
Input: 
S = "gforks"
Q = 2
index[] = {0, 4}
sources[] = {"g", "ks"}
targets[] = {"geeks", "geeks"}
Output: 
geeksforgeeks
Explanation:
"g" starts at index 0, so, it's replaced by
"geeks". Similarly, "ks" starts at index 4,
and is replaced by "geeks".
Example 2:
Input: 
S = "gforks"
Q = 2
index[] = {0, 3}
sources[] = {"g", "ss"}
targets[] = {"geeks", "geeks"}
Output: 
geeksforks
Explanation:
"g" starts at index 0, so, it's replaced by
"geeks". "ss" doesn't start at index 3 in
original S, so it's not replaced.
Your Task:
You don't need to read input or print anything. You only need to complete the function findAndReplace() that takes a string S, an integer Q, and 3 arrays index, sources, and targets of size Q, as input and returns the new string after all the operations. index[i], sources[i], and targets[i] denotes the index, sources, and targets for i_{th} query.
Expected Time Complexity:  O(|S| * Q)
Expected Auxilliary Space: O(Q)
 
Constraints:
1 ≤ |S| ≤ 10^{4}
1 ≤ Q ≤ 100
1 ≤ length of sources_{i}, targets_{i} ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def findAndReplace(self, S, Q, index, sources, targets):

        # code here 

Solutions:
class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		replacements = [(index[i], sources[i], targets[i]) for i in range(Q)]
		replacements.sort(reverse=True)
		for (i, source, target) in replacements:
			if S[i:i + len(source)] == source:
				S = S[:i] + target + S[i + len(source):]
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		rlen = 0
		for x in range(Q):
			substr = S[index[x] + rlen:index[x] + len(sources[x]) + rlen]
			if substr == sources[x]:
				S = S[0:index[x] + rlen] + targets[x] + S[index[x] + len(sources[x]) + rlen:]
				rlen += len(targets[x]) - len(substr)
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		x = ''
		i = 0
		while i < len(S):
			if len(index) and i == index[0]:
				j = i
				k = 0
				while j < len(S) and k < len(sources[0]) and (sources[0][k] == S[j]):
					j += 1
					k += 1
				if k == len(sources[0]):
					x = x + targets[0]
					i = j
				else:
					x = x + S[i]
					i += 1
				sources.pop(0)
				targets.pop(0)
				index.pop(0)
			else:
				x = x + S[i]
				i += 1
		return x


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		res = []
		i = 0
		while i < len(S):
			if i in index:
				temp = index.index(i)
				if S[i:i + len(sources[temp])] == sources[temp]:
					res.append(targets[temp])
				else:
					res.append(S[i:i + len(sources[temp])])
				i += len(sources[temp])
				continue
			else:
				res.append(S[i])
			i += 1
		return ''.join(res)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		valid_queries = list(filter(lambda x: S[x[0]:x[0] + len(x[1])] == x[1], zip(index, sources, targets)))
		valid_queries.sort()
		diff = 0
		res = S
		for (i, s, t) in valid_queries:
			res = res[:i + diff] + t + res[i + diff + len(s):]
			diff += len(t) - len(s)
		return res


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		prev = 0
		cnt = 0
		for i in range(Q):
			if S[index[i]:index[i] + len(sources[i])] == sources[i]:
				St = list(S)
				tar = list(targets[i])
				St[index[i]:index[i] + len(sources[i])] = tar
				S = ''.join(map(str, St))
				if i != Q - 1:
					prev += len(targets[i])
					cnt += len(sources[i])
					index[i + 1] = prev + index[i + 1] - cnt
			elif i != Q - 1:
				index[i + 1] = prev + index[i + 1] - cnt
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		index.reverse()
		sources.reverse()
		targets.reverse()
		for (i, j) in enumerate(index):
			if S[j:].startswith(sources[i]):
				S = S[:j] + targets[i] + S[j + len(sources[i]):]
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		for i in range(Q):
			n = len(sources[-i - 1])
			j = index[-i - 1]
			if S[j:j + n] == sources[-i - 1]:
				S = S[:j] + targets[-i - 1] + S[j + n:]
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		index.reverse()
		sources.reverse()
		targets.reverse()
		for (i, j, k) in zip(index, sources, targets):
			if S[i:i + len(j)] == j:
				S = S[0:i] + k + S[i + len(j):]
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		idx = []
		for i in range(Q):
			if S.find(sources[i], index[i]) == index[i]:
				idx.append(i)
		for i in idx:
			S = S[:index[i]] + targets[i] + S[index[i] + len(sources[i]):]
			for j in range(i + 1, Q):
				index[j] += len(targets[i]) - len(sources[i])
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		replace_index = []
		for i in range(Q):
			if S.find(sources[i], index[i], index[i] + len(sources[i])) == index[i]:
				replace_index.append(i)
		if not replace_index:
			return S
		offset = 0
		for i in replace_index:
			cur_index = index[i] + offset
			S = S[:cur_index] + S[cur_index + len(sources[i]):]
			S = S[:cur_index] + targets[i] + S[cur_index:]
			offset += len(targets[i]) - len(sources[i])
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		d = {}
		for i in range(Q):
			if S[index[i]:len(sources[i]) + index[i]] == sources[i]:
				d[index[i]] = [sources[i], targets[i]]
		ans = ''
		n = len(S)
		i = 0
		while i < n:
			if i in d:
				ans = ans + d[i][1]
				i = i + len(d[i][0])
			else:
				ans = ans + S[i]
				i += 1
		return ans


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		res = []
		beg = 0
		for i in range(Q):
			ind = index[i]
			if S[ind:ind + len(sources[i])] == sources[i]:
				res.append(S[beg:ind])
				res.append(targets[i])
				beg = ind + len(sources[i])
		res.append(S[beg:len(S)])
		return ''.join(res)


class Solution:

	def findAndReplace(self, S, Q, indices, sources, targets):
		data = sorted(zip(indices, sources, targets), reverse=True)
		for (i, s, t) in data:
			if S[i:i + len(s)] == s:
				S = S[:i] + t + S[i + len(s):]
		return S


class Solution:

	def findAndReplace(self, s, Q, index, sources, targets):
		for i in range(Q - 1, -1, -1):
			if s[index[i]:len(sources[i]) + index[i]] == sources[i]:
				s = s[:index[i]] + targets[i] + s[index[i] + len(sources[i]):]
		return s


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		diff = 0
		for j in range(len(index)):
			x = sources[j]
			y = targets[j]
			i = index[j]
			if x == S[i + diff:i + diff + len(x)]:
				S = S[:i + diff] + y + S[i + diff + len(x):]
				diff += len(y) - len(x)
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		n = len(S)
		res = ''
		i = 0
		while i < n:
			j = 0
			while j < Q:
				if i == index[j]:
					if S[i:i + len(sources[j])] == sources[j]:
						res += targets[j]
						i += len(sources[j]) - 1
						break
				j += 1
			if j == Q:
				res += S[i]
			i += 1
		return res


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		sortd = []
		for i in range(Q):
			sortd.append([index[i], i])
		sortd.sort(reverse=True)
		for ind in sortd:
			i = ind[0]
			s = sources[ind[1]]
			t = targets[ind[1]]
			if S[i:i + len(s)] == s:
				S = S[0:i] + t + S[i + len(s):]
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		index.reverse()
		sources.reverse()
		targets.reverse()
		for (ind, so, tar) in zip(index, sources, targets):
			if S[ind:ind + len(so)] == so:
				S = S[0:ind] + tar + S[ind + len(so):]
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		res = list(S)
		for i in range(Q):
			start = index[i]
			end = index[i] + len(sources[i])
			if S[start:end] == sources[i]:
				res[index[i]] = targets[i]
				for i in range(start + 1, end):
					res[i] = ''
		return ''.join(res)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		ans = ''
		j = 0
		for (i, s, t) in zip(index, sources, targets):
			while j < i:
				ans += S[j]
				j += 1
			if S[j:j + len(s)] == s:
				ans += t
				j += len(s)
		while j < len(S):
			ans += S[j]
			j += 1
		return ans


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		arr = []
		for k in range(Q):
			ind = index[k]
			pat = sources[k]
			flag = True
			i = ind
			for j in range(len(pat)):
				if i >= len(S) or S[i] != pat[j]:
					flag = False
					break
				i += 1
			if flag == True:
				arr.append(k)
		temp = 0
		for i in range(len(arr)):
			ind = index[arr[i]] + temp
			temp += len(targets[arr[i]]) - len(sources[arr[i]])
			prefix = S[:ind]
			suffix = S[ind + len(sources[arr[i]]):]
			S = prefix + targets[arr[i]] + suffix
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		c = 0
		m = {}
		for i in range(Q):
			d = S.find(sources[i], index[i])
			if d == index[i]:
				m[d] = [len(sources[i]), targets[i]]
		t = ''
		i = 0
		n = len(S)
		while i < n:
			if i in m:
				t += m[i][1]
				i += m[i][0]
			else:
				t += S[i]
				i += 1
		return t


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		new = S
		prevt = 0
		prevs = 0
		l2 = 0
		for i in range(Q):
			l = int(len(sources[i]))
			upto = index[i] + l
			l2 += l
			if S[index[i]:upto] == sources[i]:
				new = new[:index[i] + prevt - prevs] + targets[i] + S[index[i] + l:]
				prevt += len(targets[i])
				prevs += len(sources[i])
		return new


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		a = S[:]
		s = 0
		for (i, j, k) in sorted(zip(index, sources, targets)):
			if S[i:i + len(j)] == j:
				i = i + s
				a = a[:i] + k + a[i + len(j):]
				s += len(k) - len(j)
		return a


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		S = list(S)
		to_replace_target = []
		to_replace_source = []
		for q_no in range(Q):
			i = index[q_no]
			n = len(sources[q_no])
			if S[i:i + n] == list(sources[q_no]):
				S[i:i + n] = ['$'] * n
				to_replace_target.append(targets[q_no])
				to_replace_source.append(sources[q_no])
		S = ''.join(S)
		for i in range(len(to_replace_target)):
			S = S.replace('$' * len(to_replace_source[i]), to_replace_target[i], 1)
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		l = len(S)
		ans = ''
		i = 0
		while i < l:
			if i in index:
				a = index.index(i)
				s = sources[a]
				t = targets[a]
				if i + len(s) <= l:
					b = S[i:i + len(s)]
					if b == s:
						ans += t
						i += len(s)
					else:
						ans += S[i]
						i += 1
				else:
					ans += S[i]
					i += 1
			else:
				ans += S[i]
				i += 1
		return ans


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		te = S
		S = list(S)
		for i in range(Q):
			if sources[i] in te:
				ind = te.find(sources[i], index[i])
			else:
				ind = -1
			if index[i] == ind:
				S[index[i]] = targets[i]
				for j in range(ind + 1, len(sources[i]) + ind):
					S[j] = ''
		return ''.join(S)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		answer = ''
		input_idx = 0
		read_idx = 0
		while read_idx < len(S):
			if input_idx == Q:
				answer += S[read_idx:]
				return answer
			if read_idx == index[input_idx]:
				(src, trg) = (sources[input_idx], targets[input_idx])
				(st, ed) = (read_idx, read_idx + len(src))
				if S[st:ed] == src:
					answer += trg
					read_idx = ed
				else:
					answer += S[read_idx]
					read_idx += 1
				input_idx += 1
			else:
				answer += S[read_idx]
				read_idx += 1
		return answer


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		res = []
		i = 0
		while i < len(S):
			if i in index:
				temp = index.index(i)
				if S[i:i + len(sources[temp])] == sources[temp]:
					res.append(targets[temp])
				else:
					res.append(S[i:i + len(sources[temp])])
				i += len(sources[temp])
				continue
			else:
				res.append(S[i])
			i += 1
		return ''.join(res)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		Q = int(input())
		index = list(map(int, input().split()))
		sources = list(map(str, input().split()))
		targets = list(map(str, input().split()))
		ob = Solution()
		print(ob.findAndReplace(S, Q, index, sources, targets))


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		for (i, s, t) in sorted(zip(index, sources, targets), key=lambda x: x[0], reverse=True):
			if S[i:i + len(s)] == s:
				S = S[:i] + t + S[i + len(s):]
		return S
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		Q = int(input())
		index = list(map(int, input().split()))
		sources = list(map(str, input().split()))
		targets = list(map(str, input().split()))
		ob = Solution()
		print(ob.findAndReplace(S, Q, index, sources, targets))


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		index.reverse()
		sources.reverse()
		targets.reverse()
		for (ind, so, tar) in zip(index, sources, targets):
			if S[ind:ind + len(so)] == so:
				S = S[0:ind] + tar + S[ind + len(so):]
		return S
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		Q = int(input())
		index = list(map(int, input().split()))
		sources = list(map(str, input().split()))
		targets = list(map(str, input().split()))
		ob = Solution()
		print(ob.findAndReplace(S, Q, index, sources, targets))


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		n = len(S)
		diff = 0
		for i in range(Q):
			curr_ind = index[i]
			curr_s = sources[i]
			curr_t = targets[i]
			m = len(curr_s)
			p = len(curr_t)
			if curr_ind + diff + m <= n:
				if S[curr_ind + diff:curr_ind + diff + m] == curr_s:
					new = S[:curr_ind + diff] + curr_t + S[curr_ind + diff + m:]
					diff += p - m
					n += p - m
					S = new
		return S
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		Q = int(input())
		index = list(map(int, input().split()))
		sources = list(map(str, input().split()))
		targets = list(map(str, input().split()))
		ob = Solution()
		print(ob.findAndReplace(S, Q, index, sources, targets))


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		org = S
		for i in range(Q - 1, -1, -1):
			l = 0
			m = 0
			source = sources[i]
			s_ind = index[i]
			while l < len(source):
				if S[s_ind] == source[l]:
					l += 1
					s_ind += 1
				else:
					break
			if l == len(source):
				temp = S[:index[i]] + targets[i] + S[s_ind:]
				S = temp
		return S
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		Q = int(input())
		index = list(map(int, input().split()))
		sources = list(map(str, input().split()))
		targets = list(map(str, input().split()))
		ob = Solution()
		print(ob.findAndReplace(S, Q, index, sources, targets))


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		lookup = {i: (src, tgt) for (i, src, tgt) in zip(index, sources, targets)}
		res = ''
		i = 0
		while i < len(S):
			if i in lookup:
				(ptn, tar) = lookup[i]
				if S[i:].startswith(ptn):
					res += tar
					i += len(ptn)
				else:
					res += S[i]
					i += 1
			else:
				res += S[i]
				i += 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		Q = int(input())
		index = list(map(int, input().split()))
		sources = list(map(str, input().split()))
		targets = list(map(str, input().split()))
		ob = Solution()
		print(ob.findAndReplace(S, Q, index, sources, targets))


class Solution:

	def findAndReplace(self, S, q, ind, so, tar):
		ind.reverse()
		so.reverse()
		tar.reverse()
		for (i, s, t) in zip(index, sources, targets):
			if S[i:i + len(s)] == s:
				S = S[:i] + t + S[i + len(s):]
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		test = S
		z = 0
		for i in range(0, len(index)):
			x = sources[i]
			y = len(x)
			if S[index[i]:index[i] + y] == x:
				test = test[:index[i] + z] + targets[i] + test[index[i] + y + z:]
				z = z + len(targets[i]) - y
		S = test
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		indexEnum = []
		for (i, val) in enumerate(index):
			indexEnum.append((i, val))
		indexEnum.sort(reverse=True)
		for (i, index) in indexEnum:
			s = sources[i]
			t = targets[i]
			if s == S[index:index + len(s)]:
				S = ''.join([S[:index], t, S[index + len(s):]])
		return S


class Solution:

	def find(self, S, source, index):
		l = len(source)
		for i in range(l):
			if S[index + i] != source[i]:
				return -1
		return 1

	def replaceStr(self, S, index, source, target):
		s1 = S[index:]
		S = S[:index]
		s1 = s1.replace(source, target, 1)
		S += s1
		return S

	def findAndReplace(self, S, Q, index, sources, targets):
		for i in range(Q - 1, -1, -1):
			if self.find(S, sources[i], index[i]) != -1:
				S = self.replaceStr(S, index[i], sources[i], targets[i])
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		arr = [i for i in S]
		for i in range(Q):
			if sources[i] == ''.join(arr[index[i]:index[i] + len(sources[i])]):
				arr[index[i]] = targets[i]
				for x in range(index[i] + 1, index[i] + len(sources[i])):
					arr[x] = ''
		return ''.join(arr)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		string = []
		(st, j) = ('', 0)
		rep = -1
		i = 0
		while i < len(S):
			if j < Q:
				if i == index[j]:
					if S[i:i + len(sources[j])] == sources[j]:
						if j == Q - 1:
							rep = 1
						string.append(st)
						string.append(targets[j])
						i += len(sources[j])
						j += 1
						st = ''
					else:
						j += 1
						st += S[i]
						i += 1
				else:
					st += S[i]
					i += 1
			else:
				st += S[i]
				i += 1
		string.append(st)
		return ''.join(string)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		modified = list(S)
		for (idx, source, target) in zip(index, sources, targets):
			if not S[idx:].startswith(source):
				continue
			else:
				modified[idx] = target
				for i in range(idx + 1, len(source) + idx):
					modified[i] = ''
		return ''.join(modified)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		index.reverse()
		sources.reverse()
		targets.reverse()
		for (i, s, t) in zip(index, sources, targets):
			if S[i:i + len(s)] == s:
				S = S[0:i] + t + S[i + len(s):]
		return S


class Solution:

	def findAndReplace(self, s, q, index, sources, targets):
		arr = [(index[i], sources[i], targets[i]) for i in range(q)]
		arr.sort()
		d = []
		for i in range(q):
			m = len(arr[i][1])
			if s[index[i]:arr[i][0] + m] == arr[i][1]:
				d.append(i)
		c = 0
		ans = ''
		i = 0
		j = 0
		n = len(d)
		while i < len(s) and j < n:
			m = len(arr[d[j]][1])
			ans += s[i:arr[d[j]][0]]
			i = arr[d[j]][0] + m
			ans += arr[d[j]][2]
			j += 1
		ans += s[i:]
		return ans


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		word = ''
		i = j = 0
		while i < len(S):
			if j < len(index) and index[j] == i:
				till = index[j] + len(sources[j])
				str1 = S[index[j]:till]
				if sources[j] in str1:
					word += targets[j]
					i += len(sources[j]) - 1
				else:
					word += S[i]
				j += 1
			else:
				word += S[i]
			i += 1
		return word


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		sNew = ''
		i = 0
		currIndex = 0
		while i < Q:
			if i == 0 and index[i] != 0:
				sNew = sNew + S[0:index[i]]
			currIndex = index[i]
			indexSub = len(sources[i])
			if S[currIndex:currIndex + indexSub] == sources[i]:
				sNew = sNew + targets[i]
			else:
				sNew = sNew + S[currIndex:currIndex + indexSub]
			i += 1
			if i == Q:
				sNew = sNew + S[index[i - 1] + indexSub:]
				return sNew
			sNew = sNew + S[index[i - 1] + indexSub:index[i]]


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		idx = {index[i]: i for i in range(len(index))}
		(in_window, i, j, end, valid) = (False, 0, 0, -1, False)
		(ans, sr_idx, s) = ([], -1, '')
		while i < len(S):
			if i in idx:
				in_window = True
				end = i + len(sources[idx[i]])
				(sr_idx, j, valid) = (idx[i], 0, True)
				s = ''
			if not in_window:
				ans.append(S[i])
			else:
				s += S[i]
				if i == end - 1:
					if valid and S[i] == sources[sr_idx][j]:
						ans.append(targets[sr_idx])
					else:
						ans.append(s)
					in_window = False
					s = ''
				elif S[i] == sources[sr_idx][j]:
					j += 1
				else:
					valid = False
			i += 1
		return ''.join(ans)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		n = len(S)
		m = 0
		for i in range(Q - 1, -1, -1):
			idx = index[i]
			s = sources[i]
			t = targets[i]
			if S[idx:idx + len(s)] == s:
				S = S[:idx] + t + S[idx + len(s):]
				m = len(t) - 1
		return S


class Solution:

	def findAndReplace(self, s, Q, index, sources, targets):
		list_new = []
		ctr = 0
		range_list = [x for x in range(0, len(s))]
		range_list_iter = iter(range_list)
		steps = 0
		i = 0
		for r in range_list_iter:
			if r in index:
				try:
					indexing = s.index(sources[ctr], r)
				except:
					indexing = -1
					list_new.append(s[r])
					ctr += 1
					continue
				if r == indexing:
					list_new.append(targets[ctr])
				else:
					list_new.append(s[r])
					ctr += 1
					continue
				leng = len(sources[ctr]) - 1
				if leng > 0:
					while i < leng:
						try:
							next(range_list_iter)
						except StopIteration:
							break
						i += 1
				i = 0
				ctr += 1
				if ctr > len(index) - 1 and r >= len(s):
					break
			else:
				list_new.append(s[r])
		return ''.join(list_new)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		ans = ''
		pos = 0
		for i in range(Q):
			idx = index[i]
			if S[idx:idx + len(sources[i])] == sources[i]:
				ans += S[pos:idx]
				ans += targets[i]
				pos = idx + len(sources[i])
		ans += S[pos:len(S)]
		return ans


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		listChanges = []
		for i in range(Q):
			l = len(sources[i])
			start = index[i]
			end = start + l
			if S[start:end] == sources[i]:
				listChanges.append(i)
			else:
				pass
		extra = 0
		for j in range(len(listChanges)):
			i = listChanges[j]
			l = len(sources[i])
			t = len(targets[i])
			start = extra + index[i]
			end = start + l
			S = S[0:start] + targets[i] + S[end:]
			extra += t - l
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		leng = 0
		for i in range(len(index)):
			index[i] += leng
			if S[index[i]:index[i] + len(sources[i])] != sources[i]:
				continue
			str = S[:index[i]] + targets[i] + S[index[i] + len(sources[i]):]
			S = str
			leng += len(targets[i]) - len(sources[i])
		return S


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		st = 0
		res = []
		for (i, src, tgt) in zip(index, sources, targets):
			if S[i:].startswith(src):
				res.extend(S[st:i])
				res.extend(tgt)
				st = i + len(src)
		if st < len(S):
			res.extend(S[st:len(S)])
		return ''.join(res)


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		s = S[:]
		toBeAdded = 0
		for i in range(Q):
			sourceLen = len(sources[i])
			if S[index[i]:index[i] + sourceLen] == sources[i]:
				s = s[:index[i] + toBeAdded] + targets[i] + S[index[i] + sourceLen:]
				toBeAdded += len(targets[i]) - sourceLen
		return s


class Solution:

	def findAndReplace(self, S, Q, index, sources, targets):
		for (index, sources, targets) in sorted(zip(index, sources, targets), reverse=True):
			if S[index:index + len(sources)] == sources:
				S = S[:index] + targets + S[index + len(sources):]
			else:
				S = S
		return S