Two employees of a well-known company, Alice and Bob, have proposed their solutions to a critical bug that occurred. Now Alice suspects that Bob simply took her code and added non-functional characters to create the impression of more intensive work.
The company writes code in an esoteric programming language similar to Malbolge, so each employee's code is represented as a string of lowercase Latin letters. Alice's code is represented by the string $$$t$$$, and Bob's code is represented by the string $$$s$$$.
Since Bob's keyboard is broken, he can only type exactly two characters at a time, meaning he can insert any two (not necessarily identical) characters into any position in the string. After Alice expressed her suspicion of Bob's plagiarism, their team leader started analyzing the strings $$$s$$$ and $$$t$$$ to determine if Bob could have obtained string $$$s$$$ from string $$$t$$$ using his broken keyboard. To do this, he tries to gradually remove pairs of adjacent characters from string $$$s$$$ until he obtains string $$$t$$$.
Help determine if Bob is guilty of plagiarism: determine if it is possible to obtain string $$$t$$$ from string $$$s$$$ by removing pairs of adjacent characters any number of times.
The first line contains a string $$$s$$$ consisting of lowercase Latin letters from 'a' to 'z' ($$$1 \le |s| \le 2 \cdot 10^5$$$).
The second line contains a string $$$t$$$, also consisting of lowercase Latin letters ($$$1 \le |t| \le |s|$$$).
Output «YES» if string $$$t$$$ can be obtained from string $$$s$$$ by removing pairs of adjacent characters, and «NO» otherwise.
Points are awarded for each subtask only if all tests of that subtask and the necessary subtasks are passed.
| Subtask | Points | Additional Constraints | Necessary Subtasks | Test Case Information |
| 1 | 20 | $$$|s| \le 10$$$ | full | |
| 2 | 23 | $$$t$$$ consists only of 'a' | first error | |
| 3 | 27 | $$$|s| \le 1000$$$; $$$|t| = |s| - 2$$$ | first error | |
| 4 | 30 | none | 1 – 3 | first error |
sobaka baka
YES
sobabka baka
NO
abacaba aca
YES
Отвлечемся от задач про программистов и перенесемся в совершенно обыкновенные ясли, где мальчик Вова (3 годика) практикуется в устном счете, а если точнее — в вычислении арифметических выражений по модулю $$$10^9 + 7$$$.
Совсем недавно Вова придумал длинное и очень красивое арифметическое выражение. Выражение состяло из $$$n$$$ целых неотрицательных чисел, меньших $$$10^9 + 7$$$, и знаков сложения и умножения между ними. Первым же делом он вычислил это выражение по модулю $$$10^9 + 7$$$, после чего выписал само выражение и результат на лист бумаги. Все числа он выписал без ведущих нулей.
Пока шел тихий час, Вова спал, а хулиганы стерли несколько цифр в выражении и заменили их на другие. Менять знаки или результат вычисления выражения хулиганы не решились, даже для них это слишком низко. Когда Вова проснулся, он обнаружил рядом с его листочком ластик и карандаш. У Вовы есть принципы — если хулиганы изменили не более двух цифр, то он их простит, иначе они будут наказаны по всей строгости ясельных законов.
К сожалению, чтобы понять, сколько цифр изменили хулиганы, Вове явно понадобится ваша помощь. Определите, могло ли данное выражение быть получено из верного равенства заменой не более двух цифр, и если да, то в каких числах и какие цифры были изменены.
Единственная строка входного файла содержит выражение, которое обнаружил Вова у себя на листке. Выражение состоит из двух частей, разеделенных знаком '='.
Первая часть содержит $$$n$$$ целых неотрицательных чисел, разделенных знаками сложения ('+') и умножения ('*') ($$$1 \le n \le 10^5$$$). Вторая часть — целое неотрицательное число, означающее результат вычисления выражения.
Числа и все знаки разделяются одним пробелом. Гарантируется, что все числа строго меньше $$$10^9 + 7$$$ и записаны без ведущих нулей.
В случае, если данное выражение не может быть получено из верного равенства заменой не более двух цифр, выведите «NO».
В противном случае в первой строке выведите «YES». На следующей строке выведите целое число $$$k \leq 2$$$ — количество чисел, которые были изменены.
В следующих $$$k$$$ строках выведите по два числа — позицию измененнного числа в выражении (от $$$1$$$ до $$$n$$$) и его исходное значение.
Суммарно должно быть изменено не более двух цифр. В процессе замены в числах не должны появиться ведущие нули и числа должны остаться меньше $$$10^9 + 7$$$. Если существует несколько вариантов ответа, выведите любой из них.
Баллы за поздадачи 1 – 6 начисляются только в случае, если все тесты соответствующей подзадачи и необходимых подзадач, а также тесты из условия, успешно пройдены.
Подзадача 7 оценивается потестово — всего в ней 25 тестов, каждый из которых независимо оценивается в 1 балл.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 7 | $$$n \le 45$$$ | первая ошибка | |
| 2 | 13 | $$$n \le 100$$$ | 1 | первая ошибка |
| 3 | 15 | все числа в выражении меньше $$$10$$$ | первая ошибка | |
| 4 | 12 | нет операций умножения | первая ошибка | |
| 5 | 13 | нет операций сложения | первая ошибка | |
| 6 | 15 | все числа в выражении меньше $$$10^5$$$ | 3 | первая ошибка |
| 7 | 25 | нет | 1 – 6 | потестовая оценка |
В подзадачах 3 и 6 ограничение касается только чисел слева от знака равенства, результат вычисления выражения может быть произвольным числом, меньшим $$$10^9 + 7$$$.
56 + 14 * 86 + 51 * 55 = 3925
YES 1 3 76
97 + 14 * 31 * 76 + 99 * 73 = 40930
NO