Description

Hint: A brief and formalized statement is provided at the end of the description.

A train called SFM consists of $n$ carriages, numbered from $1$ to $n$. Carriage indexed $i$ has comfort $a_i\in \{0,1\}$, where $1$ stands for comfortable, and $0$ stands for uncomfortable. We want to minimize the indices of comfortable carriages, in other words, to maximize the lexicographical order of $a$.

In order to do that, we have another train consists also $n$ carriages, whose comfortable numbers are denoted by $b_i\in \{0,1\}$. There are $m$ operations available, the $i$-th operation has two parameters $l_i,r_i$, which denotes swapping $a_k$ and $b_k$ for every $k\in [l_i,r_i]$.

You can choose to perform or not to perform the operations in a given order. There are $2^m$ ways to do that, so we turned to you to choose the best one to maximize the lexicographical order of $a$. You only need to output the final result.

Formally: Two binary string $a,b$ are given, whose length are both $n$. Also, $2m$ integers $l_i,r_i$ is given. For $i=1,2,\ldots,m$, by this order, excecute the precedure:

• Choose to perform $i$-th operation or not.
  • If so, for $k=l_i,l_i+1,\cdots,r_i$, swap $a_k$ and $b_k$.

You need to maximize the lexicographical order of $a$ and output the final result.

Input Format

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

The second line contains a binary string $a$, where $a_i$ is the comfort of the train SFM.

The second line contains a binary string $b$, where $b_i$ is the comfort of another train.

The following $m$ lines, the $i$-th line contains two integers $l_i,r_i$, to describe the $i$-th operation.

Output Format

Output one line containing a binary string—the best result after the operations.

10 5
0101011001
0101001110
5 10
2 6
1 10
6 6
3 4

0101011110

Hint

本题采用捆绑测试。

• Subtask 1 (20 pts): $1\le n,m\le 20$;
• Subtask 2 (30 pts)：$l_i$ are pairwise distinct, $a_i \ne b_i$;
• Subtask 3 (30 pts)：$1 \le n ,m \le 10^3$;
• Subtask 4 (20 pts)：No further constraints.

It is guaranteed that

• $1\le n,m\le 2\times 10^5$;
• $1\le l_i\le r_i\le n$.