T512993 Strange Train Game (English ver.)

[Chinese statement](https://www.luogu.com.cn/problem/T467091). **You must submit your code at the Chinese version of the statement.**

**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.

无

无

**本题采用捆绑测试。** - 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$.