You have two binary strings $a$ and $b$ of length $n$. You would like to make all the elements of both strings equal to $0$. Unfortunately, you can modify the contents of these strings using only the following operation:
- You choose two indices $l$ and $r$ ($1 \le l \le r \le n$);
- For every $i$ that respects $l \le i \le r$, change $a_i$ to the opposite. That is, $a_i := 1 - a_i$;
- For every $i$ that respects either $1 \le i < l$ or $r < i \le n$, change $b_i$ to the opposite. That is, $b_i := 1 - b_i$.
Your task is to determine if this is possible, and if it is, to find such an appropriate chain of operations. The number of operations should not exceed $n + 5$. It can be proven that if such chain of operations exists, one exists with at most $n + 5$ operations.
/*
cf1750C
对于每个操作,a序列和b序列都是互补的,若所有[ai = bi]并且a != b,则无法操作成0
现在a,b互补,可以对a进行运算。(1,n)k可使a成b
假设ai = bi = 1,并尝试在不改变其他条件的情况下,使得ai = bi = 0。
若i > 1,则只需(1,i)和(1,i - 1)
若i = 1, 则只需(1,n)和(2,n)
由于n > 1总是可以运算的,因此我们找到了2 * n + o(1)运算的解决方法,
在将其优化至n + 5即可
*/