Аня занимается рукоделием. Сегодня она решила связать платок из полупрозрачных ниток. Каждая нитка характеризуется единственным целым числом — коэффициентом прозрачности.
Платок делается по следующей схеме: выбираются горизонтальные нитки с коэффициентами прозрачности \(a_1, a_2, \ldots, a_n\) и вертикальные с коэффициентами прозрачности \(b_1, b_2, \ldots, b_m\). Затем они переплетаются между собой, как показано на картинке снизу, и образуют кусок ткани размера \(n \times m\), состоящий ровно из \(nm\) узлов:
Пример куска ткани при \(n = m = 4\). После того, как сплетение затянется и не будет видно зазоров между нитками, каждый узел, образованный горизонтальной ниткой с номером \(i\) и вертикальной ниткой с номером \(j\), превратится в клетку, которую мы будем обозначать как \((i, j)\). Клетка \((i, j)\) будет иметь коэффициент прозрачности \(a_i + b_j\).
Интересностью полученного платка будем называть количество его подквадратов\(^{\dagger}\), в которых нет пары соседних\(^{\dagger \dagger}\) клеток с одинаковыми коэффициентами прозрачности.
Аня ещё не решила, из каких ниток плести платок, поэтому вам будут даны также \(q\) запросов увеличения/уменьшения коэффициентов прозрачностей ниток на некоторых отрезках. После каждого запроса надо вывести интересность полученного платка.
\(^{\dagger}\)Подквадратом куска ткани называется множество всех его клеток \((i, j)\), таких что \(x_0 \le i \le x_0 + d\) и \(y_0 \le j \le y_0 + d\) для некоторых целых чисел \(x_0\), \(y_0\) и \(d\) (\(1 \le x_0 \le n - d\), \(1 \le y_0 \le m - d\), \(d \ge 0\)).
\(^{\dagger \dagger}\)Клетки \((i_1, j_1)\) и \((i_2, j_2)\) считаются соседними, если \(|i_1 - i_2| + |j_1 - j_2| = 1\).
Примечание
В первом примере коэффициенты прозрачности клеток в получившемся платке равны:
Тогда есть следующие подквадраты, не содержащие двух соседних по вертикали или по горизонтали клеток с одинаковым коэффициентом прозрачности:
- Каждая из \(16\) клеток по отдельности;
- Подквадрат с левым верхним углом в клетке \((3, 1)\) и правым нижним углом в клетке \((4, 2)\);
- Подквадрат с левым верхним углом в клетке \((2, 3)\) и правым нижним углом в клетке \((3, 4)\);
- Подквадрат с левым верхним углом в клетке \((2, 1)\) и правым нижним углом в клетке \((3, 2)\);
- Подквадрат с левым верхним углом в клетке \((3, 3)\) и правым нижним углом в клетке \((4, 4)\).
Во втором примере после первого запроса коэффициенты прозрачности горизонтальных ниток равны \([1, 2, 2]\). После второго запроса коэффициенты прозрачности вертикальных ниток равны \([2, -4, 2]\).