F. Директор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Совсем недавно Карам стал директором школы, но какой же может быть директор без своей печати? Поэтому Карам решил заказать себе с RiliExpress $$$n$$$ печатей, $$$i$$$-я из которых представляет собой матрицу $$$h_i$$$ на $$$w_i$$$, где в некоторых клетках есть краска.

Но оказалось, что эти печати работают немного по другому: если её прикладывают на клетчатую бумагу, то в клетках, где соприкоснулась краска, цвет меняется на противоположный. Все печати применяются на одном листе.

Караму стало интересно, что будет, если каждую из печатей применить $$$x_i$$$ раз в позициях $$${0, 1,..., x_i - 2, x_i-1}$$$. После этого он захотел узнать, сколько клеток покрашены. Для понимания процесса применения печатей посмотрите примечания к примерам.

Входные данные

В первой строке даётся одно целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество печатей. Далее следует описание печатей.

Первая строка описания содержит 3 положительных целых числа $$$h_i,w_i$$$ $$$(1 \le h_i \cdot w_i \le 10^5)$$$ и $$$x_i$$$ $$$(1 \le x_i \le 10^9)$$$ — размеры печати и сколько раз её применяют. Гарантируется что сумма размеров печатей не превосходит $$$10^5$$$.

В следующих $$$h_i$$$ строках находятся строки из $$$w_i$$$ символов «0» или «1» — сама печать, где символ «1» означает, что в этой клетке есть краска.

Выходные данные

Выведите ответ на задачу.

Система оценки

Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы.

ГруппаДополнительные ограниченияБаллыНеобходимые подгруппы
$$$0$$$Тесты из условия$$$0$$$—
$$$1$$$$$$n=1, x_i=1$$$$$$7$$$—
$$$2$$$$$$x_i=1$$$$$$9$$$$$${1}$$$
$$$3$$$$$$x_i \le 10$$$$$$15$$$$$${1,2}$$$
$$$4$$$$$$n=1$$$$$$23$$$$$${1}$$$
$$$5$$$$$$h_i \le 10, x_i \le 10^5$$$$$$21$$$$$${0,1}$$$
$$$6$$$—$$$25$$$$$${0,1,2,3,4,5}$$$
Примеры
Входные данные
1
2 2 2
11
11
Выходные данные
4
Входные данные
2
2 2 1
11
00
1 1 2
1
Выходные данные
4
Входные данные
1
3 3 2
110
010
111
Выходные данные
6
Примечание

Рассмотрим 1 и 3 примеры, для удобства при применении нового штампа новые клетки будут голубыми, а клетки, которые поменяют цвет на белый, будем обозначать штриховкой.

Рассмотрим 1 пример, после применения печати закрашено $$$4$$$ клетки:

процесс использования печати в позициях $$$x={0,1}$$$ в первом примере.

Рассмотрим 3 пример, после применения печати закрашено $$$6$$$ клеток:

процесс использования печати в позициях $$$x={0,1}$$$ в третьем примере.