题目背景

English statement. You must submit your code at the Chinese version of the statement.

SFM 团队又断网了，于是玩起了 Mini Metro，结果发现游戏更新了，列车要自己组装，于是有了这题。

题目描述

提示：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

SFM 号列车由 $n$ 节车厢组成，编号为 $1\sim n$。每节车厢有一个舒适度 $a_i\in \{0,1\}$，$0$ 代表不舒适，$1$ 代表舒适。管理组想要让舒适的车厢的编号尽量小，也就是说，让 $a$ 的字典序最大。

为此，管理组运来了一辆 $n$ 节车厢的备用车，舒适度表示为 $b_i\in \{0,1\}$。共有 $m$ 个可进行的操作，第 $i$ 个操作的操作参数为 $l_i,r_i$，表示 $\forall l_i\le k\le r_i$，交换 $a_k,b_k$。

可以从小到大依次决定是否执行每个操作，但是一共有 $2^m$ 种方案，于是，管理组找来了你，帮忙选出一种最优的方案，最大化 $a$ 的字典序。只需要输出最终得到的 $a$ 即可。

形式化地：给定长度为 $n$ 的 $01$ 串 $a,b$，给定 $2m$ 个正整数 $l_i,r_i$。对于 $i=1,2,\cdots,m$，依次执行以下操作：

• 选择是否执行第 $i$ 次操作。
  • 如果执行，则对于 $k=l_i,l_{i}+1,\cdots,r_i$，交换 $a_k,b_k$。

最大化 $a$ 的字典序并输出最终的结果。

输入格式

第一行，两个正整数 $n,m$，表示字符串的长度和操作次数。

第二行，一个长度为 $n$ 的 $01$ 串 $a$。

第三行，一个长度为 $n$ 的 $01$ 串 $b$。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$，描述第 $i$ 个操作。

输出格式

输出一行长度为 $n$ 的 $01$ 串，表示最优操作后的 $a$。

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

0101011110

提示

本题采用捆绑测试。

• Subtask 1（20 pts）：$1\le n,m\le 20$；
• Subtask 2（30 pts）：$l_i$ 互不相同，$a_i \ne b_i$；
• Subtask 3（30 pts）：$1 \le n ,m \le 10^3$；
• Subtask 4（20 pts）：无限制；

对于 $100\%$ 的数据，保证：

• $1\le n,m\le 2\times 10^5$；
• $1\le l_i\le r_i\le n$。