Информатика

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

Студент первого курса ИТМО Миша изучает новый примитивный язык программирования. В этом языке все операции производятся над массивами целых неотрицательных чисел длины \(n\).

Миша успел создать массив \(a\) и равный ему массив \(b\). Также он успел реализовать четыре функции:

1. shift — делает циклический сдвиг массива \(a\) влево на \(d\), то есть при \(a = [a_0, a_1, \ldots, a_{n-1}]\) выполняет присваивание \[a \gets [a_d, \ldots, a_{n-1}, a_0, \ldots, a_{d-1}] \text{;}\]

2. xor — присваивает в массив \(b\) его поэлементный xor (побитовое исключающее <<или>>) с массивом \(a\), то есть \[b \gets [a_0 \oplus b_0, a_1 \oplus b_1, \ldots, a_{n-1} \oplus b_{n-1}] \text{;}\]

3. and — присваивает в массив \(b\) его поэлементный and (побитовое <<и>>) с массивом \(a\);

4. or — присваивает в массив \(b\) его поэлементный or (побитовое <<или>>) с массивом \(a\).

Используя эти функции, Миша написал программу, задаваемую последовательностью операций xor, and и or длины \(m\). Программа в цикле \(p\) раз выполняет следующие действия: для каждой операции из последовательности сначала вызывается shift, а затем соответствующая этой операции функция. Так, для последовательности операций \([\mathtt{or}, \mathtt{xor}, \mathtt{and}]\) и \(p = 5\) программа будет выглядеть как

b = a = [...]
repeat 5 times {
    shift
    or
    shift
    xor
    shift
    and
}

К сожалению, язык еще новый, и его интерпретатор не справляется с выполнением такой программы. Помогите Мише определить, чему будет равно конечное состояние массива \(b\) после выполнения заданной программы.

Формат входных данных
В первой строке ввода перечислены четыре целых числа \(n\), \(m\), \(d\) и \(p\) — длина массива, количество операций в последовательности, величина сдвига и количество повторений (\(0 \le d < n \le 2 \cdot 10^5\); \(1 \le m \le 10\); \(1 \le p \le 10^9\)).

Во второй строке перечислены \(n\) целых чисел \(a_i\) — элементы массива \(a\), они же — изначальные значения элементов массива \(b\) (\(0 \le a_i \le 10^9\)).

В третьей строке через пробел перечисены \(m\) слов, каждое из которых равно <<xor>>, <<and>> или <<or>> — последовательность применяемых на каждой итерации цикла операций.

Формат выходных данных
Выведите \(n\) целых чисел — элементы массива \(b\) после выполнения описанной программы.