Вам даны две строки \(a\) и \(b\) одинаковой длины, состоящих только из символов 0 и/или 1; обе строки начинаются с символа 0 и заканчиваются символом 1.
Вы можете применять следующую операцию любое количество раз (возможно ноль раз):
- выбрать какую-то строку и два равных символа в ней; затем превратить все символы между этими двумя в эти символы.
Формально, вы выбираете одну из двух строк (обозначим ее как \(s\)), затем выбираете два символа \(l\) и \(r\), такие, что \(1 \le l < r \le |s|\) и \(s_l = s_r\), затем заменяете все символы \(s_i\), такие что \(l < i < r\) на \(s_l\).
Например, если выбранная строка это 010101, вы можете превратить ее в описанные ниже строки за одну операцию:
- 000101, если выберете \(l = 1\) и \(r = 3\);
- 000001, если выберете \(l = 1\) и \(r = 5\);
- 010001, если выберете \(l = 3\) и \(r = 5\);
- 010111, если выберете \(l = 4\) и \(r = 6\);
- 011111, если выберете \(l = 2\) и \(r = 6\);
- 011101, если выберете \(l = 2\) и \(r = 4\).
Вам нужно определить, можно ли сделать эти две строки одинаковыми при помощи применения к ним любого количества описанной выше операции.
Примечание
В первом наборе входных данных мы можем выполнить следующие операции:
- выбрать строку \(a\), \(l = 2\), \(r = 4\); после этой операции \(a\) равна 01110001, \(b\) равна 01110101;
- выбрать строку \(b\), \(l = 5\), \(r = 7\); после этой операции \(a\) равна 01110001, \(b\) равна 01110001.
Во втором наборе входных данных строки уже равны.
В третьем наборе входных данных мы можем выполнить следующие операции:
- выбрать строку \(a\), \(l = 4\), \(r = 6\); после этой операции \(a\) равна 000111, \(b\) равна 010111;
- выбрать строку \(b\), \(l = 1\), \(r = 3\); после этой операции \(a\) равна 000111, \(b\) равна 000111;
В четвертом и пятом наборах входных данных невозможно сделать строки равными.