Задача . F. Булевский компьютер

У Алисы есть компьютер, который работает с \(w\)-битными целыми числами и имеет \(n\) регистров для чисел. Текущее содержимое регистров задано как массив \(a_1, a_2, \ldots, a_n\).

Компьютер использует так называемые «супер функции», каждая из которых принимает два входных регистра и считает некую функцию, используя те два регистра. Учтите, что вы можете использовать один и тот же регистр как два входных аргумента.

Каждая «супер функция» состоит из логических функций. Существует шесть логических функций: AND, OR, XOR, NOT AND, NOT OR и NOT XOR, которые обозначаются как «A», «O», «X», «a», «o», «x», соответственно. Каждая битовая функция принимает два входных бита. Их результаты с учетом входных данных \(b_1\), \(b_2\) приведены ниже:

«Супер функция», которая состоит из \(w\) логических операций, разделяет два входных числа \(x_1\) и \(x_2\) на \(w\) бит, выполняет \(i\)-ю логическую операцию с \(i\)-и битами двух входных чисел. После чего соединяет эти \(w\) бит и возвращает это число.

Например, для \(4\)-битного компьютера мы можем иметь функцию «AXoA» (AND, XOR, NOT OR, AND). Для двух входных чисел: \(13 = 1101_2\) и \(10 = 1010_2\), функция вернет \(12 = 1100_2\), так как \(1\) AND \(1\) равно \(1\), \(1\) XOR \(0\) равно \(1\), NOT (\(0\) OR \(1\)) равно \(0\) и \(1\) AND \(0\) равно \(0\).

Вам дан список всех \(m\) функций. Для каждой функции вам нужно найти количество упорядоченных пар переменных, которые на выходе дадут \(0\). Другими словами, найдите количество упорядоченных пар \((i,j)\), где \(1 \leq i,j \leq n\), таких что \(w_k(a_i, a_j) = 0\), где \(w_k\) — \(k\)-я функция, которую использует «супер функция».