AT_abc419_d [ABC419D] Substr Swap

You are given length- $ N $ lowercase English strings $ S $ and $ T $ , and $ M $ pairs of integers $ (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M) $ . Perform the following operation for $ i=1,2,\ldots,M $ in order: - Swap the $ L_i $ -th through $ R_i $ -th characters of $ S $ and the $ L_i $ -th through $ R_i $ -th characters of $ T $ . - For example, if $ S $ is `abcdef`, $ T $ is `ghijkl`, and $ (L_i,R_i)=(3,5) $ , then $ S $ and $ T $ become `abijkf` and `ghcdel`, respectively. Find the string $ S $ after performing the $ M $ operations.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ S $ $ T $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_M $ $ R_M $

Output the $ S $ after performing the $ M $ operations.

### Sample Explanation 1 Initially, $ S $ and $ T $ are `apple` and `lemon`, respectively. - After the operation for $ i=1 $ , $ S $ and $ T $ are `aemoe` and `lppln`, respectively. - After the operation for $ i=2 $ , $ S $ and $ T $ are `lppln` and `aemoe`, respectively. - After the operation for $ i=3 $ , $ S $ and $ T $ are `lpple` and `aemon`, respectively. Thus, the string $ S $ after the three operations is `lpple`. ### Constraints - $ 1\leq N\leq 5\times 10^5 $ - $ 1\leq M\leq 2\times 10^5 $ - Each of $ S $ and $ T $ is a length- $ N $ lowercase English strings. - $ 1\leq L_i\leq R_i\leq N $ - $ N $ , $ M $ , $ L_i $ , and $ R_i $ are integers.