This is an exercise of cumulative sums.

For each position, if we know how many times the characters are swapped, then the final \(S\) can be obtained. Specifically, the \(i\)-th character of the answer is \(S_i\) if that position was swapped an even number of times, and \(T_i\) if odd. The number of swaps can be computed fast using cumulative sums. The computational complexity is \(O(N+M)\).

N, M = map(int, input().split())
s = input()
t = input()
cum = [0] * (N + 1)
for _ in range(M):
    l, r = map(int, input().split())
    cum[l - 1] += 1
    cum[r] -= 1
for i in range(N):
    cum[i + 1] += cum[i]
ans = [s[i] if cum[i] % 2 == 0 else t[i] for i in range(N)]
print("".join(ans))