Обозначим размер максимального паросочетания в графе \(G\) как \(\mathit{MM}(G)\).
Задан двудольный граф. Вершины первой доли пронумерованы от \(1\) до \(n\). Вершины второй доли пронумерованы от \(n+1\) до \(2n\). Степень каждой вершины равна \(2\).
Для четверки целых чисел \((l, r, L, R)\), где \(1 \le l \le r \le n\) и \(n+1 \le L \le R \le 2n\), определим \(G'(l, r, L, R)\) как граф, который состоит из всех вершин заданного графа, которые находятся либо в отрезке \([l, r]\), либо в отрезке \([L, R]\), и всех ребер заданного графа таких, что вершины их концов принадлежат одному из этих отрезков. Другими словами, чтобы получить граф \(G'(l, r, L, R)\) из изначального графа, надо удалить все вершины \(i\) такие, что \(i \notin [l, r]\) и \(i \notin [L, R]\), и все инцидентные им ребра.
Посчитайте сумму \(\mathit{MM}(G(l, r, L, R))\) по всем наборам целых чисел \((l, r, L, R)\) таких, что \(1 \le l \le r \le n\) and \(n+1 \le L \le R \le 2n\).
Выходные данные
Выведите одно целое число — сумму \(\mathit{MM}(G(l, r, L, R))\) по всем наборам целых чисел \((l, r, L, R)\), у которых \(1 \le l \le r \le n\) и \(n+1 \le L \le R \le 2n\).