8026번 - Pionek 다국어

Rozważmy nieskończoną (we wszystkich kierunkach) planszę o kwadratowych polach. Na tej planszy stoi pionek na polu o współrzędnych $(1,1)$. Pionek ten może wykonywać pewne ruchy. Może się on przesuwać o pewne ustalone liczby pól w prawo bądź w lewo oraz o pewne ustalone liczby pól w górę bądź w dół.

Przy takich ograniczeniach można zwykle dojść pionkiem tylko do niektórych pól planszy. Twoim zadaniem jest określić, ile spośród takich osiągalnych pól mieści się w pewnym prostokątnym fragmencie planszy.

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $n$ oraz $m$ ($1 ≤ n, m ≤ 200\,000$) oznaczające odpowiednio liczbę ruchów poziomych oraz pionowych, jakie może wykonać pionek za jednym skokiem.

W drugim wierszu znajdują się cztery liczby całkowite $x_1$, $y_1$, $x_2$, $y_2$ ($-10^9 ≤ x_1, y_1, x_2, y_2 ≤ 10^9$) oznaczające odpowiednio współrzędne lewego dolnego i prawego górnego wierzchołka prostokątnego fragmentu planszy, w którym należy policzyć liczbę pól osiągalnych. Przyjmujemy, że punkt $(x,y)$ należy do tego prostokąta wtedy i tylko wtedy, gdy $x_1 ≤ x ≤ x_2$ oraz $y_1 ≤ y ≤ y_2$.

W każdym z następnych $n$ wierszy znajduje się jedna liczba całkowita $a_i$ ($1 ≤ a_i ≤ 10^{18}$) oznaczająca liczbę pól o jakie pionek może się przesunąć w prawo lub w lewo wykonując $i$-ty poziomy ruch.

W każdym z następnych $m$ wierszy znajduje się jedna liczba całkowita $b_i$ ($1 ≤ b_i ≤ 10^{18}$) oznaczająca liczbę pól o jakie pionek może się przesunąć w górę lub w dół wykonując $i$-ty pionowy ruch.

Twój program powinien wypisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą oznaczającą liczbę pól w obrębie zadanego prostokątnego fragmentu planszy, do których pionek może się dostać.