Устный счет
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Отвлечемся от задач про программистов и перенесемся в совершенно обыкновенные ясли, где мальчик Вова (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 балл.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
17$$$n \le 45$$$первая ошибка
213$$$n \le 100$$$1первая ошибка
315все числа в выражении меньше $$$10$$$первая ошибка
412нет операций умноженияпервая ошибка
513нет операций сложенияпервая ошибка
615все числа в выражении меньше $$$10^5$$$3первая ошибка
725нет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