Maximizing Train Carriage Comfort

You are given two binary strings a and b, each of length n, representing the comfort level (0 for uncomfortable, 1 for comfortable) of the train carriages on an SFM train. The train has n carriages numbered from 1 to n. The manager wishes to maximize the lexicographical order of a (i.e. have as many comfortable carriages as possible in the earlier positions) by selectively swapping segments with a spare train.

You are also given m operations. The i-th operation is parameterized by two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n), meaning that if you choose to perform this operation, then for every index k with l_i ≤ k ≤ r_i you swap the values a[k] and b[k].

The operations are considered in order from 1 to m. For each operation you may decide independently whether to execute it or not. After processing all operations, the configuration of a is finalized and printed.

Formal description:

Given two binary strings a and b (each of length n) and m operations (each described by two positive integers l_i and r_i), for i = 1, 2, …, m decide whether to perform the i-th operation. If you perform it, then for every k with l_i ≤ k ≤ r_i, swap a[k] and b[k]. The goal is to maximize the lexicographical order of a. Output the final a after all operations.

Note: For indices where a[i] and b[i] are the same, swapping has no effect. In indices where they differ, note that if (a[i], b[i]) = (0,1) then not swapping gives 0 while swapping gives 1, whereas if (a[i], b[i]) = (1,0) then not swapping gives 1 but swapping gives 0. Hence, ideally, you want to have a[i] = 1 for all positions if possible – that is, to achieve the string which is the bitwise OR of the original a and b in every position. However, since the swapping operations come with fixed intervals and must be applied in order, you may not be able to obtain the ideal string. Your task is to choose a subset of operations (applied in order) that produces the lexicographically maximum possible final a.

inputFormat

The first line contains two integers n and m — the number of carriages and the number of operations, respectively.

The second line contains a binary string a of length n.

The third line contains a binary string b of length n.

The following m lines each contain two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n), describing an operation.

outputFormat

Output a binary string of length n representing the final configuration of a that is lexicographically maximal.

sample

2 1
01
10
1 2

10