Марк любит быстро перемещаться. Поэтому он создал космический корабль, перемещающийся в \(4\)-мерном пространстве.
Он хочет использовать космический корабль для выполнения миссий как можно быстрее. В каждой миссии космический корабль стартует из точки \((0, 0, 0, 0)\) и должен оказаться в точке \((a, b, c, d)\). Для этого он дает команду компьютеру корабля выполнить серию перемещений, где каждое перемещение — это единичный шаг по одной из восьми сторон света: \((\pm 1, 0, 0, 0)\), \((0, \pm 1, 0, 0)\), \((0, 0, \pm 1, 0)\), \((0, 0, 0, \pm 1)\).
К сожалению, постройка космического корабля также шла очень быстро, поэтому в коде космического корабля есть ошибка. Первый ход будет выполнен один раз, второй — два, третий — три и так далее. В общем случае \(i\)-й ход будет выполнен \(i\) раз.
Для любых четырех целых чисел \(a, b, c, d\) пусть \(f(a, b, c, d)\) — минимальное количество ходов миссии, которая заканчивается в точке \((a, b, c, d)\). Вычислите сумму \(f(a, b, c, d)\) по всем точкам (с целочисленными координатами), таким, что \(-A\le a\le A\), \(-B\le b\le B\), \(-C\le c\le C\), \(-D\le d\le D\).
Выходные данные
Выведите сумму \(f(a, b, c, d)\) по множеству точек, описанному в условии.
Примечание
В первом примере необходимо вычислить \(f(-1, 0, 0, 0)+f(0, 0, 0, 0) + f(1, 0, 0, 0) = 1 + 0 + 1 = 2\).
Во втором примере необходимо вычислить сумму \(f(a, b, c, d)\) по \(27\) различным точкам \((a, b, c, d)\). Опишем значение \(f(a, b, c, d)\) для некоторых из них:
- Выполняется условие \(f(-1, 0, 0, -1)=3\), которое достигается следующей последовательностью перемещений (стрелка \(\xrightarrow{\pm i}\) обозначает, что перемещение выполняется по \(i\)-й координате): \(\)(0, 0, 0, 0) \xrightarrow{-1} (-1, 0, 0, 0) \xrightarrow{+4} (-1, 0, 0, 2) \xrightarrow{-4} (-1, 0, 0, -1).\(\)
- Выполняется условие \(f(1, 1, 0, 1) = 5\), и оно достигается следующей последовательностью ходов: \(\)(0, 0, 0, 0) \xrightarrow{+1} (1, 0, 0, 0) \xrightarrow{-2} (1, -2, 0, 0) \xrightarrow{+2} (1, 1, 0, 0) \xrightarrow{-4} (1, 1, 0, -4) \xrightarrow{+4} (1, 1, 0, 1).\(\)
В третьем примере необходимо вычислить сумму \(f(a, b, c, d)\) по \(7\cdot5\cdot 9\cdot 3\) точкам. Одна из них — \((3, 2, 4, 1)\). Она имеет значение \(f(3, 2, 4, 1) = 4\) и может быть достигнута следующей последовательностью ходов: \(\)(0, 0, 0, 0) \xrightarrow{+4} (0, 0, 0, 1) \xrightarrow{+2} (0, 2, 0, 1) \xrightarrow{+1} (3, 2, 0, 1) \xrightarrow{+3} (3, 2, 4, 1).\(\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 0 0 0
|
2
|
|
2
|
1 1 0 1
|
82
|
|
3
|
3 2 4 1
|
4616
|