Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chefland is a big city which consists of infinite number of junctions on a 2D plane. The junctions are depicted below and they form a hexagonal grid — they satisfy the following conditions:
Two of the junctions have coordinates $(0,0)$ and $(1,0)$.
Each junction $J$ is connected by line segments with six other junctions. These junctions are the vertices of a regular hexagon with side length $1$ and their distances from $J$ are also all equal to $1$.

Chef created a robot that can traverse the junctions. Initially, it is in some junction and oriented towards another junction which is connected to it by a line segment. The robot accepts a string of instructions — decimal digits $0$ through $5$. It executes the instructions one by one and stops after executing the final instruction. When the robot executes an instruction denoted by a digit $d$, it first rotates by $60 \cdot d$ degrees counterclockwise and then moves $1$ unit forward, to the junction it is oriented towards.

Chef wants to test the robot, so he wrote a string $S$ of $N$ instructions. You should answer $Q$ queries. In each query, Chef wants to give the robot a substring of instructions $S_{L}, S_{L+1}, \ldots, S_{R}$; the robot starts in the junction $(0, 0)$ and it is oriented towards $(1, 0)$. You should find the final position (the $x$- and $y$-coordinates) of the robot.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The second line contains a single string $S$ with length $N$.
$Q$ lines follow. Each of these lines contains two space-separated integers $L$ and $R$ describing a query.

------  Output ------
For each query, print a single line containing two space-separated real numbers — the coordinates of the robot. Your answer will be considered correct if the absolute or relative error of each coordinate does not exceed $10^{-6}$.

Warning: Outputting more than 8 digits after floating point may result in exceeding output size limit and receiving "Runtime error" verdict.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ N, Q ≤ 2 \cdot 10^{5}$
$1 ≤ L ≤ R ≤ N$
$S$ contains only characters '0', '1', '2', '3', '4' and '5'
the sum of $N$ over all test cases does not exceed $10^{6}$
the sum of $Q$ over all test cases does not exceed $10^{6}$

------  Example Input ------

1
3 3
012
1 1
1 2
2 2

------  Example Output ------

1.00000000 0.00000000
1.50000000 0.86602540
0.50000000 0.86602540

Difficulty: VERY_HARD
Tags: Geometry

Range queries

Segment trees revisited

Mathematics

Data structures
Skill types: Data structures

Range queries

Starter code:

Solutions:
sin = {}
cos = {}
sin[0] = 0
sin[60] = pow(3, 0.5) / 2
sin[120] = sin[60]
sin[180] = 0
sin[240] = -sin[60]
sin[300] = -sin[60]
cos[0] = 1
cos[60] = 0.5
cos[120] = -0.5
cos[180] = -1
cos[240] = -0.5
cos[300] = 0.5
import math
for ij in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	Position = {}
	Angle = {}
	x = 0
	y = 0
	A = 0
	d = 60
	i = 0
	Position[i] = (0, 0)
	Angle[i] = 0
	for item in s:
		A = A + 60 * int(item)
		if A >= 360:
			A = A % 360
		i = i + 1
		Position[i] = (Position[i - 1][0] + cos[A], Position[i - 1][1] + sin[A])
		Angle[i] = A
	for h in range(q):
		(L, R) = map(int, input().split())
		pr = Position[R]
		p1 = Position[L - 1]
		moveinx = pr[0] - p1[0]
		moveiny = pr[1] - p1[1]
		i = Angle[L - 1]
		ci = math.cos(i * math.pi / 180)
		si = math.sin(i * math.pi / 180)
		ans1 = moveinx * ci + moveiny * si
		ans2 = -moveinx * si + moveiny * ci
		print('%.8f' % ans1, '%.8f' % ans2)


import math
for i in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	positions = [[0, 0]]
	ang_x_axis = [0]
	start_x = 0
	start_y = 0
	st_ang = 0
	for j in s:
		st_ang += 60 * int(j)
		deg = math.pi * st_ang / 180
		start_x += math.cos(deg)
		start_y += math.sin(deg)
		positions.append([start_x, start_y])
		ang_x_axis.append(deg)
	for j in range(q):
		(l, r) = map(int, input().split())
		new_pt = [positions[r][0] - positions[l - 1][0], positions[r][1] - positions[l - 1][1]]
		ang = ang_x_axis[l - 1]
		new_pt_1 = [round(new_pt[0] * math.cos(ang) + new_pt[1] * math.sin(ang), 8), round(-new_pt[0] * math.sin(ang) + new_pt[1] * math.cos(ang), 8)]
		print(*new_pt_1)


import math

def rotate(n, x, y):
	n = -n
	x1 = x * math.cos(n * math.pi / 3) - y * math.sin(n * math.pi / 3)
	y1 = x * math.sin(n * math.pi / 3) + y * math.cos(n * math.pi / 3)
	return (x1, y1)

def solve():
	(n, q) = map(int, input().split())
	inp = input()
	pre_x = [0]
	pre_y = [0]
	track = [0]
	for i in inp:
		s = (track[-1] + int(i)) % 6
		pre_x.append(pre_x[-1] + store[s][0])
		pre_y.append(pre_y[-1] + store[s][1])
		track.append(s)
	for i in range(q):
		(l, r) = map(int, input().split())
		x = pre_x[r] - pre_x[l - 1]
		y = pre_y[r] - pre_y[l - 1]
		(x, y) = rotate(track[l - 1], x, y)
		print('%.8f %.8f' % (x, y))
y_diff = math.sqrt(3) / 2
store = {0: (1.0, 0.0), 1: (0.5, y_diff), 2: (-0.5, y_diff), 3: (-1.0, 0.0), 4: (-0.5, -y_diff), 5: (0.5, -y_diff)}
for t in range(int(input())):
	solve()


from math import sin, cos, radians

def rotate(facing, instruction):
	degrees = instruction * 60
	facing += degrees
	return facing % 360
dx = [1, 0.5, -0.5, -1, -0.5, +0.5]
val = 3 ** 0.5 / 2
dy = [0, val, val, 0, -val, -val]

def move(x, y, facing):
	return (x + dx[facing // 60], y + dy[facing // 60])
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = [int(i) for i in input()]
	path = {0: (0, 0, 0)}
	(x, y) = (0, 0)
	facing = 0
	for i in range(1, n + 1):
		facing = rotate(facing, s[i - 1])
		(x, y) = move(x, y, facing)
		path[i] = (x, y, facing)
	for _ in range(q):
		(l, r) = map(int, input().split())
		(x, y) = path[r][:2]
		(x0, y0, angle) = path[l - 1]
		angle = radians(angle)
		x -= x0
		y -= y0
		x1 = x * cos(angle) + y * sin(angle)
		y1 = -x * sin(angle) + y * cos(angle)
		print(round(x1, 8), round(y1, 8))


import math
testCase = int(input())
for t in range(testCase):
	(n, q) = [int(x) for x in input().split()]
	s = input()
	array = []
	prevCoord = (0, 0)
	prevAngle = 0
	array.append((prevCoord, prevAngle))
	for c in s:
		angleDeg = prevAngle + 60 * int(c)
		angleRad = angleDeg % 360 * (math.pi / 180)
		curr = (prevCoord[0] + math.cos(angleRad), prevCoord[1] + math.sin(angleRad))
		array.append((curr, angleDeg))
		prevCoord = curr
		prevAngle = angleDeg % 360
	for i in range(q):
		(l, r) = [int(x) for x in input().split()]
		lCoord = array[l - 1]
		rCoord = array[r]
		(x, y) = (rCoord[0][0] - lCoord[0][0], rCoord[0][1] - lCoord[0][1])
		x1 = x * math.cos(-1 * lCoord[1] * math.pi / 180) - y * math.sin(-1 * lCoord[1] * math.pi / 180)
		y1 = y * math.cos(-1 * lCoord[1] * math.pi / 180) + x * math.sin(-1 * lCoord[1] * math.pi / 180)
		print(round(x1, 8), round(y1, 8))


from math import sin, cos, radians
t = int(input())
while t:
	(n, q) = input().split(' ')
	n = int(n)
	q = int(q)
	s = input()
	inst = [int(i) for i in s]
	angle = radians(60)
	prefixsum = []
	prefixc = []
	prefixs = []
	prefixcosine = []
	prefixsine = []
	prefixsum.append(inst[0])
	prefixc.append(cos(prefixsum[0] * angle))
	prefixs.append(sin(prefixsum[0] * angle))
	prefixcosine.append(prefixc[0])
	prefixsine.append(prefixs[0])
	for i in range(1, n):
		prefixsum.append(inst[i] + prefixsum[i - 1])
		prefixc.append(cos(prefixsum[i] * angle))
		prefixs.append(sin(prefixsum[i] * angle))
		prefixcosine.append(prefixc[i] + prefixcosine[i - 1])
		prefixsine.append(prefixs[i] + prefixsine[i - 1])
	for z in range(q):
		(l, r) = input().split(' ')
		l = int(l)
		r = int(r)
		l = l - 1
		r = r - 1
		if l == 0:
			x = prefixcosine[r]
			y = prefixsine[r]
		else:
			x = prefixc[l - 1] * (prefixcosine[r] - prefixcosine[l - 1]) + prefixs[l - 1] * (prefixsine[r] - prefixsine[l - 1])
			y = prefixc[l - 1] * (prefixsine[r] - prefixsine[l - 1]) - prefixs[l - 1] * (prefixcosine[r] - prefixcosine[l - 1])
		print('%0.8f' % x, '%0.8f' % y)
	t -= 1


import math

def calcdist(l, r):
	if l == 0:
		return distances[0][r][:2]
	a = 0
	while distances[a][l - 1][2] != 0:
		a += 1
	xcoord = distances[a][r][0] - distances[a][l - 1][0]
	ycoord = distances[a][r][1] - distances[a][l - 1][1]
	return [xcoord, ycoord]
d = [[2, 0, 0], [1, 1, 1], [-1, 1, 2], [-2, 0, 3], [-1, -1, 4], [1, -1, 5]]
t = int(input())
for x in range(t):
	(n, q) = map(int, input().split())
	s = input()
	distances = [[[0, 0, 0] for a in range(n)] for b in range(6)]
	for b in range(6):
		num = int(s[0])
		distances[b][0] = d[(num + b) % 6]
	for a in range(1, n):
		num = int(s[a])
		for b in range(6):
			old = distances[b][a - 1]
			newdir = (old[2] + num) % 6
			distances[b][a] = [old[0] + d[newdir][0], old[1] + d[newdir][1], newdir]
	for y in range(q):
		(l, r) = map(int, input().split())
		dist = calcdist(l - 1, r - 1)
		print('{0:.8f}'.format(dist[0] / 2), '{0:.8f}'.format(dist[1] * math.sqrt(3) / 2))


import math
N = math.sqrt(3)

def rotate(x, y, direc):
	if direc == 0:
		return [round(x, 6), round(y, 6)]
	if direc == 5:
		return [round((x - N * y) / 2, 6), round((N * x + y) / 2, 6)]
	elif direc == 4:
		return [round(-(x + N * y) / 2, 6), round((N * x - y) / 2, 6)]
	elif direc == 3:
		return [round(-x, 6), round(-y, 6)]
	elif direc == 2:
		return rotate(-x, -y, 5)
	return rotate(-x, -y, 4)
t = int(input())
for i in range(t):
	(n, q) = list(map(int, input().split()))
	com = str(input())
	arr = [[0, 0, 0]]
	direct = 0
	for j in range(n):
		direct = (direct + int(com[j])) % 6
		x = arr[j][0]
		y = arr[j][1]
		if direct == 0:
			x += 1
		elif direct == 1:
			x += 0.5
			y += 0.5
		elif direct == 2:
			x -= 0.5
			y += 0.5
		elif direct == 3:
			x -= 1
		elif direct == 4:
			x -= 0.5
			y -= 0.5
		else:
			x += 0.5
			y -= 0.5
		arr.append([x, y, direct])
	for j in range(q):
		(l, r) = list(map(int, input().split()))
		print(*rotate(arr[r][0] - arr[l - 1][0], N * (arr[r][1] - arr[l - 1][1]), arr[l - 1][2]))


from math import sqrt

def solve():
	(n, q) = map(int, input().split())
	s = input()
	p = [0, 0, 0]
	d = 0
	xs = [0]
	ys = [0]
	zs = [0]
	ds = [0]
	for i in s:
		i = int(i)
		d = (d + i) % 6
		if d == 0:
			p[0] += 1
		elif d == 1:
			p[1] += 1
		elif d == 2:
			p[2] += 1
		elif d == 3:
			p[0] -= 1
		elif d == 4:
			p[1] -= 1
		elif d == 5:
			p[2] -= 1
		xs.append(p[0])
		ys.append(p[1])
		zs.append(p[2])
		ds.append(d)
	for _ in range(q):
		(l, r) = map(int, input().split())
		d1 = ds[l - 1]
		x1 = xs[l - 1]
		y1 = ys[l - 1]
		z1 = zs[l - 1]
		x2 = xs[r]
		y2 = ys[r]
		z2 = zs[r]
		xq = x2 - x1
		yq = y2 - y1
		zq = z2 - z1
		z = 0
		x = 0
		y = 0
		if d1 == 0:
			x = xq
			y = yq
			z = zq
		elif d1 == 1:
			x = yq
			y = zq
			z = -xq
		elif d1 == 2:
			x = zq
			y = -xq
			z = -yq
		elif d1 == 3:
			x = -xq
			y = -yq
			z = -zq
		elif d1 == 4:
			x = -yq
			y = -zq
			z = xq
		elif d1 == 5:
			x = -zq
			y = xq
			z = yq
		a = x + y / 2 - z / 2
		b = (z + y) * sqrt(3) / 2
		print('%.8f %.8f' % (a, b))
t = int(input())
for _ in range(t):
	solve()


dx = [1, 0, -1, -1, 0, 1]
dy = [0, 1, 1, 0, -1, -1]
sr3p2 = 3 ** 0.5 / 2
coss = [1, 0.5, -0.5, -1, -0.5, 0.5]
sins = [0, sr3p2, sr3p2, 0, -sr3p2, -sr3p2]
for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	instr = input()
	cum = [None] * N
	dr = 0
	(x, y) = (0, 0)
	for i in range(N):
		dr = (dr + int(instr[i])) % 6
		(x, y) = (x + dx[dr], y + dy[dr])
		cum[i] = (dr, x, y)
	for _ in range(Q):
		(L, R) = map(int, input().split())
		if L > 1:
			(ldr, lx, ly) = cum[L - 2]
		else:
			(ldr, lx, ly) = (0, 0, 0)
		(_, rx, ry) = cum[R - 1]
		(cx, cy) = (rx - lx, ry - ly)
		x = cx + cy * 0.5
		y = cy * sr3p2
		print('{0:.7f} {1:.7f}'.format(coss[ldr] * x + sins[ldr] * y, -sins[ldr] * x + coss[ldr] * y))