position = [(0,1)]
position_map = {0:1}
def grid(x,y):
while x + 1j * y not in position_map:
#print(position_map)
p,d = position[-1]
position.append((p+d,d))
position_map[p+d] = len(position)
if p+d+1j*d not in position_map: position[-1] = (p+d,d*1j)
return position_map[x + 1j * y]
# for i in range(5,-6,-1):
# for j in range(-5,6):
# print(grid(j,i),end="\t")
# print()
def sum_square_tr(n):
s = 0
for x in range(-n,0):
for y in range(-n,0):
s += grid(x,y)
return s
def eval_poly(poly,num,mod:None|int=None):
a = round(sum(v*pow(num,i,mod) for i,v in enumerate(poly)))
if mod is not None: a %= mod
return a
def mul_poly(p,q):
out = [0]*(len(p)+len(q)-1)
for i,v in enumerate(p):
for j,w in enumerate(q):
out[i+j] += v*w
return out
def add_poly(p,q):
return [a+b for a,b in zip(p,q)]
def lagrange_poly(ord,at):
poly = [1]
for i in range(ord):
if i != at:
poly = mul_poly(poly,[-i,1])
k = eval_poly(poly,at)
return [i/k for i in poly]
def fit_poly(seq):
ord = len(seq)
out = [0]*ord
for i in range(ord):
out = add_poly(out,mul_poly(lagrange_poly(ord,i),[seq[i]]))
return [i for i in out]
sqtr = [sum_square_tr(i) for i in range(6)]
#print(sqtr)
#print(fit_poly(sqtr))
def sgn(x): return 1 if x > 0 else 0 if x == 0 else -1
xpyp = [0,1,2,-4,2]
xnyp = [0,0,4,0,2]
xpyn = [0,-4,10,0,2]
xnyn = [0,-1,2,4,2]
diag = [[xnyn,xnyp],[xpyn,xpyp]]
xp = [0,19/6,-7/2,4/3]
xn = [0,13/6,5/2,4/3]
yp = [0,13/6,-5/2,4/3]
yn = [0,19/6,7/2,4/3]
col = [[xn,xp],[yn,yp]]
# assume x > y > 0
MOD = 10**9+7
def helper(x,y):
n = min(abs(x),abs(y))
N = max(abs(x),abs(y))
ygtx = abs(x) < abs(y)
sm = [x,y][ygtx]>=0
sN = [y,x][ygtx]>=0
f = n-sN
if N-n > 0 and f > 0:
return f,N-n
return ()
def rect_center(x: int,y: int): # rectangle from the lower left corner of (0,0) to lower left of (x,y)
ygtx = abs(x) < abs(y)
sm = [x,y][ygtx]>=0
sN = [y,x][ygtx]>=0
smi = -1 if (ygtx != (x >= 0)) != (y >= 0) else 1
n = min(abs(x),abs(y))
N = max(abs(x),abs(y))
sqp = diag[x >= 0][y >= 0]
square = eval_poly(sqp,n,MOD)
rp = col[ygtx][sm]
sc: int = (eval_poly(rp,N)-eval_poly(rp,n))
sc *= n
f = n-sN
sc += ((N-n)*f*(f+1))//2 * smi
if x > 0 and y < 0 and -y < x: sc -= 8*y
return (square + sc)%MOD
def rect_center_naive(x,y):
s = 0
for _x in range(min(x,0),max(x,0)):
for _y in range(min(y,0),max(y,0)):
s += grid(_x,_y)
return s
def rect(xA,yA,xB,yB):
x = sorted([xA,xB])
x[1]+=1
y = sorted([yA,yB])
y[1]+=1
s = 0
for a in [0,1]:
for b in [0,1]:
s += rect_center(x[a],y[b]) * (-1 if x[0]*x[1]>0 and abs(x[a])<abs(x[1-a]) else 1) \
* (-1 if y[0]*y[1]>0 and abs(y[b])<abs(y[1-b]) else 1)
return s
def rect_naive(xA,yA,xB,yB):
X = sorted([xA,xB])
Y = sorted([yA,yB])
s = 0
for x in range(X[0],X[1]+1):
for y in range(Y[0],Y[1]+1):
s += grid(x,y)
return s
#print("here")
#print(rect_center(3,1))
# xA = 2
# yA = -3
# ry = range(10,-10,-1)
# rx = range(-10,10)
# for y in ry:
# for x in rx:
# if abs(x)==abs(y) or x == 0 or y == 0:
# print(("*" if rect_naive(xA,yA,x,y)==rect(xA,yA,x,y) else "#")*6,end="\t")
# else:
# print((rect_naive(xA,yA,x,y)-rect(xA,yA,x,y)),end="\t")
# print()
# exit(0)
# print("-"*80)
# for y in ry:
# for x in rx:
# if abs(x)==abs(y) or x == 0 or y == 0:
# print(end="****** ")
# else:
# print(helper(x,y),end="\t")
# print()
_,q = map(int,input().split())
for i in range(q):
print(rect(*map(int,input().split())))
"""
(1,1) -> 1
(1,2) -> 2
(1,n) -> n
(2,1) -> 3
(2,2) -> 6
(2,n) -> 3n
(3,n) -> 6n
(a,b) -> b*(a*(a+1)/2)
"""
"""
diag[x >= 0][y >= 0] returns the sum of cells from (0,0) to (pm n,pm n)
col[0][x >= 0] returns the sum of cells from (0,0) to (x,1)
col[1][y >= 0] returns the sum of cells from (0,0) to (1,y)
to calculate in y > x > 0: diag[1][1] (x)
c = col[1][1] (y) - col[1][1] (x) # column from the square to the top
c * x # the rectangle at the top
- x * (x-1)/2 * (y-x) # extra since it is decreasing
y > -x > 0:
diag[0][1] (-x)
c = col[1][1] (y) - col[1][1] (-x) # column off to the right from
c * -x
+ x * (x-1)/2 * (y-x)
\ +--+ /
\| | /
*--+ /
|\ | /
| \|/
*--.-----
"""
Compilation message
spiral.cpp:6:10: error: invalid preprocessing directive #print
6 | #print(position_map)
| ^~~~~
spiral.cpp:14:3: error: invalid preprocessing directive #for
14 | # for i in range(5,-6,-1):
| ^~~
spiral.cpp:15:7: error: invalid preprocessing directive #for
15 | # for j in range(-5,6):
| ^~~
spiral.cpp:16:11: error: invalid preprocessing directive #print
16 | # print(grid(j,i),end="\t")
| ^~~~~
spiral.cpp:17:7: error: invalid preprocessing directive #print
17 | # print()
| ^~~~~
spiral.cpp:60:2: error: invalid preprocessing directive #print
60 | #print(sqtr)
| ^~~~~
spiral.cpp:61:2: error: invalid preprocessing directive #print
61 | #print(fit_poly(sqtr))
| ^~~~~
spiral.cpp:76:3: error: invalid preprocessing directive #assume
76 | # assume x > y > 0
| ^~~~~~
spiral.cpp:91:33: error: stray '#' in program
91 | def rect_center(x: int,y: int): # rectangle from the lower left corner of (0,0) to lower left of (x,y)
| ^
spiral.cpp:139:2: error: invalid preprocessing directive #print
139 | #print("here")
| ^~~~~
spiral.cpp:140:2: error: invalid preprocessing directive #print
140 | #print(rect_center(3,1))
| ^~~~~
spiral.cpp:141:3: error: invalid preprocessing directive #xA
141 | # xA = 2
| ^~
spiral.cpp:142:3: error: invalid preprocessing directive #yA
142 | # yA = -3
| ^~
spiral.cpp:143:3: error: invalid preprocessing directive #ry
143 | # ry = range(10,-10,-1)
| ^~
spiral.cpp:144:3: error: invalid preprocessing directive #rx
144 | # rx = range(-10,10)
| ^~
spiral.cpp:145:3: error: invalid preprocessing directive #for
145 | # for y in ry:
| ^~~
spiral.cpp:146:7: error: invalid preprocessing directive #for
146 | # for x in rx:
| ^~~
spiral.cpp:147:17: error: missing binary operator before token "("
147 | # if abs(x)==abs(y) or x == 0 or y == 0:
| ^
spiral.cpp:149:15: warning: extra tokens at end of #else directive [-Wendif-labels]
149 | # else:
| ^
spiral.cpp:150:15: error: invalid preprocessing directive #print
150 | # print((rect_naive(xA,yA,x,y)-rect(xA,yA,x,y)),end="\t")
| ^~~~~
spiral.cpp:151:7: error: invalid preprocessing directive #print
151 | # print()
| ^~~~~
spiral.cpp:152:3: error: invalid preprocessing directive #exit
152 | # exit(0)
| ^~~~
spiral.cpp:153:3: error: invalid preprocessing directive #print
153 | # print("-"*80)
| ^~~~~
spiral.cpp:154:3: error: invalid preprocessing directive #for
154 | # for y in ry:
| ^~~
spiral.cpp:155:7: error: invalid preprocessing directive #for
155 | # for x in rx:
| ^~~
spiral.cpp:156:17: error: missing binary operator before token "("
156 | # if abs(x)==abs(y) or x == 0 or y == 0:
| ^
spiral.cpp:158:15: warning: extra tokens at end of #else directive [-Wendif-labels]
158 | # else:
| ^
spiral.cpp:159:15: error: invalid preprocessing directive #print
159 | # print(helper(x,y),end="\t")
| ^~~~~
spiral.cpp:160:7: error: invalid preprocessing directive #print
160 | # print()
| ^~~~~
spiral.cpp:166:3: warning: missing terminating " character
166 | """
| ^
spiral.cpp:166:3: error: missing terminating " character
spiral.cpp:176:3: warning: missing terminating " character
176 | """
| ^
spiral.cpp:176:3: error: missing terminating " character
spiral.cpp:178:3: warning: missing terminating " character
178 | """
| ^
spiral.cpp:178:3: error: missing terminating " character
178 | """
| ^
spiral.cpp:184:35: error: stray '#' in program
184 | c = col[1][1] (y) - col[1][1] (x) # column from the square to the top
| ^
spiral.cpp:185:23: error: stray '#' in program
185 | c * x # the rectangle at the top
| ^
spiral.cpp:186:23: error: stray '#' in program
186 | - x * (x-1)/2 * (y-x) # extra since it is decreasing
| ^
spiral.cpp:190:36: error: stray '#' in program
190 | c = col[1][1] (y) - col[1][1] (-x) # column off to the right from
| ^
spiral.cpp:194:1: error: stray '\' in program
194 | \ +--+ /
| ^
spiral.cpp:195:2: error: stray '\' in program
195 | \| | /
| ^
spiral.cpp:197:4: error: stray '\' in program
197 | |\ | /
| ^
spiral.cpp:198:5: error: stray '\' in program
198 | | \|/
| ^
spiral.cpp:200:3: warning: missing terminating " character
200 | """
| ^
spiral.cpp:200:3: error: missing terminating " character
spiral.cpp:156: error: unterminated #else
156 | # if abs(x)==abs(y) or x == 0 or y == 0:
|
spiral.cpp:147: error: unterminated #else
147 | # if abs(x)==abs(y) or x == 0 or y == 0:
|
spiral.cpp:2:1: error: 'position' does not name a type
2 | position = [(0,1)]
| ^~~~~~~~
spiral.cpp:4:1: error: 'def' does not name a type
4 | def grid(x,y):
| ^~~
