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

Chef's friend Igzi is often at the coding gym, working out his mind muscles. When he is there, he asks Chef to guard his most prized posession: a sequence $A_{1}, A_{2}, \ldots, A_{N}$. Initially, for each $i$ ($1 ≤ i ≤ N$), $A_{i} = i$ held. However, Chef sometimes gets bored and starts playing with the sequence. Since $N$ can be very large, Chef has a lot of fun with it and he would like to share it with you.

You should process $Q$ queries of two types:
1 x: set $A_{x} = 0$
2 l r: find the maximum element in the subsequence $A_{l}, A_{l+1}, \ldots, A_{r}$

Since Chef does not want to make Igzi angry, the queries are encoded so that they have to be processed online:
For each query, let's denote the sum of answers to all previous queries of type 2, modulo $N$, by $s$. (Initially, $s = 0$.)
For each query of the first type, you are given an integer $y$. You can compute $x$ as $y + s$.
For each query of the second type, you are given two integers $p$ and $q$. You can compute $l$ as $p + s$ and $r$ as $q + s$.

------  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 following $Q$ lines describe queries.
- Each of these lines starts with an integer $t$ denoting the type of the current query: $t = 1$ for a query of the first type or $t = 2$ for a query of the second type.
- For a query of the first type, it is followed by a space and an integer $y$.
- For a query of the second type, it is followed by a space and two space-separated integers $p$ and $q$.

------  Output ------
For each query of the second type, print a single line containing one integer ― the maximum of the given subsequence.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{18}$
$1 ≤ Q ≤ 500,000$
$1 ≤ l ≤ r ≤ N$
$1 ≤ x ≤ N$
the sum of $Q$ over all test cases does not exceed $1,000,000$

------  Subtasks ------
Subtask #1 (10 points): $N, Q ≤ 1,000$

Subtask #2 (10 points): $N ≤ 100,000$

Subtask #3 (30 points): each query of the second type appears after all queries of the first type

Subtask #4 (50 points): original constraints

----- Sample Input 1 ------ 
1
7 9
2 2 5
1 0
2 -3 0
1 1
2 0 3
1 -4
1 -2
2 -4 -1
2 -5 -3
----- Sample Output 1 ------ 
5  
4
4
0
1
----- explanation 1 ------ 
- Query 1: $l = 2$, $r = 5$. The maximum element of the subsequence $A_{2}, A_{3}, A_{4}, A_{5}$ is $A_{5} = 5$. After this query, $s$ becomes $5\%7 = 5$.
- Query 2: $x = 5$. $A_{5}$ becomes $0$.
- Query 3: $l = 2$, $r = 5$. The maximum element of the same subsequence is now $A_{4} = 4$; $s$ becomes $(5+4)\%7 = 2$.
- Query 4: $x = 3$, $A_{3}$ becomes $0$.
- Query 5: $l = 2$, $r = 5$. The maximum element of the same subsequence is still $A_{4} = 4$; $s$ becomes $(5+4+4)\%7 = 6$.
- Query 6: $x = 2$, $A_{2}$ becomes $0$.
- Query 7: $x = 4$, $A_{4}$ becomes $0$.
- Query 8: $l = 2$, $r = 5$. All elements of the same subsequence as before are $0$, so the maximum is $0$; $s$ becomes $(5+4+4+0)\%7 = 6$.
- Query 9: $l = 1$, $r = 3$. The maximum of the subsequence $A_{1}, A_{2}, A_{3}$ is $A_{1} = 1$; $s$ becomes $(5+4+4+0+1)\%7 = 0$.

Difficulty: VERY_HARD
Tags: Spanning trees

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
import sys
t = int(input())

def find(leaders, r):
	if leaders[r] not in leaders:
		return leaders[r]
	else:
		stack = [r]
		temp = r
		while leaders[temp] in leaders:
			temp = leaders[temp]
			stack.append(temp)
		stack.append(leaders[temp])
		leader = stack.pop()
		while len(stack) > 0:
			x = stack.pop()
			leaders[x] = leader
		return leaders[r]
for _ in range(t):
	(n, q) = list(map(lambda x: int(x), input().split()))
	s = 0
	leaders = {}
	for _ in range(0, q):
		query = list(map(lambda x: int(x), input().split()))
		if query[0] == 1:
			y = query[1]
			x = y + s
			leaders[x] = x - 1
		if query[0] == 2:
			p = query[1]
			q = query[2]
			l = p + s
			r = q + s
			if r == 0:
				print(0)
				continue
			if r not in leaders:
				s = (s + r % n) % n
				print(r)
			else:
				answer = find(leaders, r)
				if answer < l:
					answer = 0
				s = (s + answer % n) % n
				print(answer)


def find(u):
	try:
		kk = dsu[u]
	except:
		dsu[u] = u
	while dsu[u] != u:
		try:
			u = dsu[u]
			dsu[u] = dsu[dsu[u]]
		except:
			dsu[u] = u
	return dsu[u]

def union(u, v):
	fu = find(u)
	fv = find(v)
	if fu > fv:
		dsu[fu] = dsu[fv]
	else:
		dsu[fv] = dsu[fu]
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	rank = dict()
	dsu = dict()
	s = 0
	ans = 0
	for i in range(q):
		quer = [int(o) for o in input().split()]
		ans = s % n
		if quer[0] == 1:
			x = quer[1] + ans
			union(x, x - 1)
		else:
			l = quer[1] + ans
			r = quer[2] + ans
			lll = find(r)
			if lll < l:
				print(0)
			else:
				s += lll
				print(lll)


for _ in range(int(input())):
	d = dict()
	s = 0
	query = []
	(n, q) = map(int, input().split())
	for to in range(q):
		query = list(map(int, input().split()))
		if query[0] == 1:
			d[s + query[1]] = s + query[1] - 1
		else:
			l = s + query[1]
			r = s + query[2]
			while r in d.keys():
				if d[r] in d.keys():
					d[r] = d[d[r]]
				r = d[r]
			if r < l:
				print('0')
			else:
				print(r)
				s += r
				s %= n


test = int(input())
while test > 0:
	(n, q) = map(int, input().split())
	N = {}
	s = 0
	while q > 0:
		li = list(map(int, input().split()))
		if li[0] == 1:
			x = li[1] + s
			N[x] = x - 1
		else:
			l = li[1] + s
			r = li[2] + s
			var = r
			while var >= l:
				try:
					var = N[var]
				except:
					break
			if var != r:
				N[r] = var
			if var < l:
				var = 0
			s = (s + var) % n
			print(var)
		q -= 1
	test -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = 0
	d = {}
	f = []
	for _ in range(q):
		z = list(map(int, input().split()))
		if z[0] == 1:
			k = s + z[1]
			d[k] = k - 1
		else:
			(l, r) = (z[1] + s, z[2] + s)
			while r in d:
				if d[r] in d:
					d[r] = d[d[r]]
				r = d[r]
			if r >= l:
				s += r
				s %= n
				print(r)
			else:
				print(0)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = 0
	d = dict()
	for _ in range(q):
		a = list(map(int, input().split()))
		if a[0] == 1:
			x = a[1] + s
			d[x] = x - 1
		else:
			l = a[1] + s
			r = a[2] + s
			while r in d:
				if d[r] in d:
					d[r] = d[d[r]]
				r = d[r]
			if l > r:
				print(0)
			else:
				s += r
				s %= n
				print(r)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = 0
	par = {}
	for __ in range(q):
		a = input()
		if a[0] == '1':
			x = int(a[2:]) + s
			par[x] = x - 1
		elif a[0] == '2':
			(l, r) = map(int, a[2:].split())
			l += s
			r += s
			aa = r
			st = True
			while True:
				if aa < l:
					st = False
					break
				try:
					aa = par[aa]
				except:
					break
			if aa != r:
				par[r] = aa
			if not st:
				print(0)
				aa = 0
			else:
				print(aa)
			s = (s + aa) % n


t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	d = {}
	s = 0
	total = 0
	for i in range(q):
		arr = list(map(int, input().split()))
		if arr[0] == 1:
			d[s + arr[1]] = s + arr[1] - 1
		else:
			r = arr[2] + s
			l = arr[1] + s
			while r in d:
				if d[r] in d:
					d[r] = d[d[r]]
				r = d[r]
			if r >= l:
				total += r
				print(r)
				s = total % n
			else:
				print(0)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = 0
	l = {}
	for i in range(q):
		arr = list(map(int, input().split()))
		if arr[0] == 1:
			l[s + arr[1]] = s + arr[1] - 1
		else:
			r = s + arr[2]
			while r in l:
				if l[r] in l:
					l[r] = l[l[r]]
				r = l[r]
			if r < arr[1] + s:
				print(0)
			else:
				print(r)
				s = (s + r) % n


t = int(input())
for i in range(t):
	one = {}
	s = 0
	(n, Q) = map(int, input().split())
	for j in range(Q):
		query = list(map(int, input().split()))
		if query[0] == 1:
			x = query[1] + s
			if x not in one:
				one[x] = x - 1
		elif query[0] == 2:
			maximum = 0
			l = query[1] + s
			r = query[2] + s
			while r in one:
				if one[r] in one:
					one[r] = one[one[r]]
				r = one[r]
			if r < l:
				print(0)
			else:
				print(r)
				s += r
				s = s % n


t = int(input())
for _ in range(t):
	(N, Q) = [int(v) for v in input().strip().split()]
	Aquery = {}
	SumOfAns = 0
	for i in range(Q):
		s = [int(v) for v in input().strip().split()]
		if s[0] == 1:
			Aquery[SumOfAns + s[1]] = SumOfAns + s[1] - 1
		else:
			flag = 0
			(l, r) = (SumOfAns + s[1], SumOfAns + s[2])
			x = r
			if x in Aquery:
				y = Aquery[x]
				while y in Aquery:
					y = Aquery[y]
				if y >= l:
					ans = y
				else:
					ans = 0
				Aquery[x] = y
			else:
				ans = r
			print(ans)
			SumOfAns = (SumOfAns + ans) % N


for tcs in range(int(input())):
	(n, q) = map(int, input().split())
	s = 0
	dct = {}
	for i in range(q):
		x = input().split()
		if x[0] == '1':
			x = int(x[1]) + s
			if x not in dct:
				dct[x] = x - 1
		else:
			(L, R) = (int(x[1]), int(x[2]))
			l = L + s
			r = R + s
			while r in dct:
				if dct[r] in dct:
					dct[r] = dct[dct[r]]
				r = dct[r]
			if r < l:
				print(0)
			else:
				print(r)
				s = (s + r) % n


def dofast(x, d):
	if x in d and d[x] != x:
		d[x] = dofast(d[x], d)
		return d[x]
	d[x] = x
	return x
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	d = {}
	s = 0
	for i in range(q):
		st = input().split()
		if st[0] == '1':
			sh = s + int(st[1])
			d[sh] = dofast(sh - 1, d)
		else:
			(l, r) = (s + int(st[1]), s + int(st[2]))
			temp = 0
			temp = dofast(r, d)
			if temp < l:
				temp = 0
			print(temp)
			s = (s + temp) % n


t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	s = 0
	dict1 = dict()
	for i in range(q):
		a = list(map(int, input().split()))
		if len(a) == 2:
			x = a[1] + s
			if x not in dict1:
				dict1[x] = x - 1
		else:
			(l, r) = (a[1] + s, a[2] + s)
			if r in dict1:
				temp = dict1[r]
				while True:
					if temp in dict1:
						temp = dict1[temp]
					else:
						break
				if temp >= l:
					print(temp)
					s += temp
				else:
					print(0)
				dict1[r] = temp
			else:
				print(r)
				s += r
		s = s % n


T = int(input())
maximum = max
for _ in range(T):
	(N, Q) = list(map(int, input().split()))
	s = 0
	dic = {}
	for _ in range(Q):
		li = list(map(int, input().split()))
		if li[0] == 1:
			x = s + li[1]
			if x not in dic:
				dic[x] = x - 1
		elif li[0] == 2:
			l = li[1] + s
			r = li[2] + s
			m = 0
			if r not in dic:
				m = r
			else:
				m = dic[r]
				while True:
					if m in dic:
						m = dic[m]
					else:
						break
				dic[r] = m
			if m < 0 or m < l:
				m = 0
			print(m)
			s = (s + m) % N


for i in range(int(input())):
	(n, q) = map(int, input().split())
	l = {}
	s = 0
	for j in range(q):
		query = list(map(int, input().split()))
		if query[0] == 1:
			y = query[1] + s
			l[y] = y - 1
		else:
			p = query[1] + s
			q = query[2] + s
			k = q
			while k >= p:
				if k in l:
					k = l[k]
				else:
					print(k)
					s = (s + k) % n
					break
			if q in l:
				l[q] = k
			if k < p:
				print(0)


import bisect

def binarySearch(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return 1
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return 0
for t in range(int(input())):
	(n, q) = map(int, input().split())
	ss = {}
	s = 0
	par = {}
	de = []
	for query in range(q):
		a = list(map(int, input().split()))
		if a[0] == 1:
			y = a[1]
			x = y + s
			de.append(x)
			ss[x] = 1
			par[x] = x - 1
		else:
			p = a[1]
			q = a[2]
			l = p + s
			r = q + s
			aa = r
			st = True
			while True:
				if aa < l:
					st = False
					break
				try:
					x = ss[aa]
					aa = par[aa]
				except:
					break
			if aa != r:
				par[r] = aa
			if not st:
				print(0)
				aa = 0
			else:
				print(aa)
			s = (s + aa) % n


from collections import defaultdict as dd
t = int(input())
while t:
	d = dd(int)
	pr = dd(int)
	su = 0
	(n, q) = map(int, input().split())
	while q:
		s = input()
		if s[0] == '1':
			x = int(s[2:]) + su
			d[x] = 1
			pr[x] = x - 1
		else:
			(p, qq) = map(int, s[2:].split())
			l = p + su
			r = qq + su
			a = d[r]
			x = r
			lol = 0
			while a > 0:
				x = pr[x]
				a = d[x]
				if x < l:
					lol = 1
					break
			if x != r:
				pr[r] = x
			if lol == 1:
				print(0)
				x = 0
			else:
				print(x)
			su += x
		su = su % n
		q -= 1
	t -= 1


import bisect
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = 0
	dic = dict()
	for i in range(q):
		ar = list(map(int, input().split()))
		if len(ar) == 2:
			x = s + ar[1]
			if x not in dic:
				dic[x] = x - 1
		else:
			(l, r) = (ar[1] + s, ar[2] + s)
			if r in dic:
				abc = dic[r]
				while True:
					if abc in dic:
						abc = dic[abc]
					else:
						break
				if abc >= l:
					print(abc)
					s += abc
				else:
					print(0)
				dic[r] = abc
			else:
				print(r)
				s += r
		s = s % n


for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	s = 0
	zeros = {}
	for _ in range(Q):
		(q_type, *others) = map(int, input().split())
		if q_type == 1:
			[y] = others
			x = y + s
			target = x - 1
			keys = {x}
			while target in zeros:
				keys.add(target)
				target = zeros[target]
			for key in keys:
				zeros[key] = target
		else:
			(p, q) = others
			l = p + s
			r = q + s
			i = r
			if r in zeros:
				target = r
				keys = {r}
				while target in zeros:
					keys.add(target)
					target = zeros[target]
				for key in keys:
					zeros[key] = target
				if target >= l:
					res = target
				else:
					res = 0
			else:
				res = r
			print(res)
			s += res
			s %= N