#include "hexagon.h"
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 200000, MD = 1000000007, V2 = 500000004, V6 = 166666668;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int abs_(int a) { return a > 0 ? a : -a; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int dx[] = { 1, 1, 0, -1, -1, 0 };
int dy[] = { 0, 1, 1, 0, -1, -1 };
int sum1(int n) {
return (long long) n * (n + 1) % MD * V2 % MD;
}
int sum2(int n) {
return (long long) n * (n + 1) % MD * (n * 2 + 1) % MD * V6 % MD;
}
long long cross2(int x1, int y1, int x2, int y2) {
return (long long) x1 * y2 - (long long) x2 * y1;
}
long long cross(int x0, int y0, int x1, int y1, int x2, int y2) {
return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}
int hh[N], len[N], ii[N * 2], xx[N], yy[N], xx_[N * 2 * 2 * 2], yy_[N * 2 * 2], n, n_, n1;
int compare(int i, int j) {
int i0 = i >> 1, i1 = (i0 + 1) % n, j0 = j >> 1, j1 = (j0 + 1) % n, tmp;
long long c;
if ((i & 1) != 0)
tmp = i0, i0 = i1, i1 = tmp;
if ((j & 1) != 0)
tmp = j0, j0 = j1, j1 = tmp;
if (yy[i0] != yy[j0])
return yy[i0] - yy[j0];
if (xx[i0] != xx[j0])
return xx[i0] - xx[j0];
if ((yy[i1] < yy[i0]) != (yy[j1] < yy[j0]))
return yy[i1] < yy[i0] ? -1 : 1;
c = cross(xx[i0], yy[i0], xx[i1], yy[i1], xx[j1], yy[j1]);
if (yy[i1] < yy[i0])
c = -c;
return c == 0 ? 0 : (c < 0 ? -1 : 1);
}
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int zz[1 + N], ll[1 + N], rr[1 + N], ii_[1 + N], _, u_, l_, r_;
int node(int i) {
zz[_] = rand_();
ll[_] = rr[_] = 0;
ii_[_] = i;
return _++;
}
int compare_(int i, int j) {
int i_ = (i + 1) % n, j_ = (j + 1) % n, tmp;
long long c1, c2;
if (i == j)
return 0;
if (yy[i] > yy[i_])
tmp = i, i = i_, i_ = tmp;
if (yy[j] > yy[j_])
tmp = j, j = j_, j_ = tmp;
c1 = cross(xx[i], yy[i], xx[i_], yy[i_], xx[j], yy[j]);
c2 = cross(xx[i], yy[i], xx[i_], yy[i_], xx[j_], yy[j_]);
if (c1 == 0 || c2 == 0 || (c1 > 0) == (c2 > 0))
return c1 + c2 < 0 ? -1 : 1;
c1 = cross(xx[j], yy[j], xx[j_], yy[j_], xx[i], yy[i]);
c2 = cross(xx[j], yy[j], xx[j_], yy[j_], xx[i_], yy[i_]);
return c1 + c2 > 0 ? -1 : 1;
}
void split(int u, int i) {
int c;
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
c = compare_(ii_[u], i);
if (c < 0) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (c > 0) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int first(int u) { return ll[u] == 0 ? u : first(ll[u]); }
int last(int u) { return rr[u] == 0 ? u : last(rr[u]); }
int y_;
int eval(int i) {
return xx[i] + (xx[(i + 1) % n] - xx[i]) / (yy[(i + 1) % n] - yy[i]) * (y_ - yy[i]);
}
int *ej[N * 2], eo[N * 2];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int ii1[N];
int begin_trapezoid(int i, int j) {
int i1 = ii1[i] = n1++;
ej[i1 << 1 | 0] = (int *) malloc(2 * sizeof *ej[i1 << 1 | 0]), eo[i1 << 1 | 0] = 0;
ej[i1 << 1 | 1] = (int *) malloc(2 * sizeof *ej[i1 << 1 | 1]), eo[i1 << 1 | 1] = 0;
append(i1 << 1 | 0, i1 << 1 | 1), append(i1 << 1 | 1, i1 << 1 | 0);
xx_[(i1 << 1 | 0) << 1 | 0] = eval(i), xx_[(i1 << 1 | 0) << 1 | 1] = eval(j), yy_[i1 << 1 | 0] = y_;
return i1;
}
int end_trapezoid(int i, int j) {
int i1 = ii1[i];
xx_[(i1 << 1 | 1) << 1 | 0] = eval(i), xx_[(i1 << 1 | 1) << 1 | 1] = eval(j), yy_[i1 << 1 | 1] = y_;
return i1;
}
int intersect(int i, int j) {
return min(xx_[i << 1 | 1], xx_[j << 1 | 1]) - max(xx_[i << 1 | 0], xx_[j << 1 | 0]) + 1;
}
int sum_trapezoid(int i, int z) {
int j, x, y, d;
j = i ^ 1, y = abs_(yy_[j] - yy_[i]);
if (y == 0)
return (long long) z * -intersect(i, j) % MD;
d = ((xx_[j << 1 | 1] - xx_[j << 1 | 0]) - (xx_[i << 1 | 1] - xx_[i << 1 | 0])) / y;
x = xx_[i << 1 | 1] - xx_[i << 1 | 0] + 1;
/*
* sum_{h=1}^{y-1} (x + d h) (z + h)
* = sum_{h=1}^{y-1} d h^2 + (x + z d) h + x z
* = d sum2(y - 1) + (x + z d) sum1(y - 1) + x z (y - 1)
*/
return ((long long) sum2(y - 1) * d % MD + (long long) sum1(y - 1) * (x + z * d) % MD + (long long) + (y - 1) * x % MD * z % MD) % MD;
}
void process(int i, int j) {
int l, r, p, q, type, hasi, hasj, a, b, c;
split(u_, i), hasi = u_ != 0, l = l_;
split(r_, j), hasj = u_ != 0, r = r_;
p = l ? ii_[last(l)] : -1, q = r ? ii_[first(r)] : -1, type = p != -1 && ii1[p] != -1;
if (!hasi && !hasj) {
if (type == 0)
begin_trapezoid(i, j);
else {
a = end_trapezoid(p, q), b = begin_trapezoid(p, i), c = begin_trapezoid(j, q);
append(a << 1 | 1, b << 1 | 0), append(b << 1 | 0, a << 1 | 1);
append(a << 1 | 1, c << 1 | 0), append(c << 1 | 0, a << 1 | 1);
}
u_ = merge(merge(l, merge(node(i), node(j))), r);
} else if (!hasi && hasj) {
if (type == 0)
a = end_trapezoid(j, q), b = begin_trapezoid(i, q);
else
a = end_trapezoid(p, j), b = begin_trapezoid(p, i);
append(a << 1 | 1, b << 1 | 0), append(b << 1 | 0, a << 1 | 1);
u_ = merge(merge(l, node(i)), r);
} else if (hasi && !hasj) {
if (type == 0)
a = end_trapezoid(i, q), b = begin_trapezoid(j, q);
else
a = end_trapezoid(p, i), b = begin_trapezoid(p, j);
append(a << 1 | 1, b << 1 | 0), append(b << 1 | 0, a << 1 | 1);
u_ = merge(merge(l, node(j)), r);
} else {
if (type == 0)
end_trapezoid(i, j);
else {
a = end_trapezoid(p, i), b = end_trapezoid(j, q), c = begin_trapezoid(p, q);
append(a << 1 | 1, c << 1 | 0), append(c << 1 | 0, a << 1 | 1);
append(b << 1 | 1, c << 1 | 0), append(c << 1 | 0, b << 1 | 1);
}
u_ = merge(l, r);
}
}
void trapezoidal_decomposition() {
int h, i, j, x, y;
n_ = 0, x = 0, y = 0;
for (i = 0; i < n; i++) {
xx[i] = x, yy[i] = y;
x += dx[hh[i]] * len[i], y += dy[hh[i]] * len[i];
}
n_ = 0;
for (i = 0; i < n; i++)
if (yy[i] != yy[(i + 1) % n])
ii[n_++] = i << 1 | 0, ii[n_++] = i << 1 | 1;
sort(ii, 0, n_);
memset(ii1, -1, n * sizeof *ii1), n1 = 0, _ = 1;
for (h = 0; h < n_; h += 2) {
i = ii[h] >> 1, j = ii[h + 1] >> 1;
y_ = yy[(ii[h] & 1) == 0 ? i : (i + 1) % n], process(i, j);
}
}
int dfs(int p, int i, int d) {
int o, sum;
sum = (long long) d * (xx_[i << 1 | 1] - xx_[i << 1 | 0] + 1) % MD;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
sum = (sum + dfs(i, j, d + abs_(yy_[i] - yy_[j]))) % MD;
if ((i ^ j) == 1)
sum = (sum + sum_trapezoid(i, d)) % MD;
else
sum = (sum - (long long) d * intersect(i, j)) % MD;
}
}
return sum;
}
int solve() {
int i, ans;
trapezoidal_decomposition();
ans = 0;
for (i = 0; i < n1 * 2; i++)
if (yy_[i] == 0 && xx_[i << 1 | 0] <= 0 && 0 <= xx_[i << 1 | 1]) {
ans = dfs(-1, i, 0);
break;
}
for (i = 0; i < n1 * 2; i++)
free(ej[i]);
return ans;
}
int draw_territory(int n_, int a, int b, vi hh_, vi len_) {
int h, i, x, y, ans1, ans2;
long long area2, boundary, internal;
n = n_;
for (i = 0; i < n; i++)
hh[i] = hh_[i] - 1, len[i] = len_[i];
x = 0, y = 0, area2 = 0, boundary = 0;
for (i = 0; i < n; i++) {
h = hh[i];
area2 += cross2(x, y, x + dx[h] * len[i], y + dy[h] * len[i]);
boundary += len[i];
x += dx[h] * len[i], y += dy[h] * len[i];
}
if (area2 < 0)
area2 = -area2;
internal = (area2 - boundary) / 2 + 1;
ans1 = (boundary + internal) % MD;
ans2 = 0;
for (h = 0; h < 3; h++) {
ans2 = (ans2 + solve()) % MD;
for (i = 0; i < n; i++)
hh[i] = (hh[i] + 1) % 6;
}
if (ans2 < 0)
ans2 += MD;
ans2 = (long long) ans2 * V2 % MD;
return ((long long) ans1 * a + (long long) ans2 * b) % MD;
}
