Given two numbers $N$ and $\mbox{M}$. $N$ indicates the number of elements in the array $A[](1-indexed)$ and $\mbox{M}$ indicates number of queries. You need to perform two types of queries on the array $\boldsymbol{A\left[\right]}$.  

You are given $\mbox{M}$ queries. Queries can be of two types, type 1 and type 2.  

Type 1 queries are represented as 1 i j : Modify the given array by removing elements from $\boldsymbol{i}$ to $j$ and adding them to the front.  

Type 2 queries are represented as 2 i j : Modify the given array by removing elements from $\boldsymbol{i}$ to $j$ and adding them to the back.  

Your task is to simply print $\left|A[1]-A[N]\right|$ of the resulting array after the execution of $\mbox{M}$ queries followed by the resulting array.  

Note While adding at back or front the order of elements is preserved.  

Input Format

First line consists of two space-separated integers, $N$ and $\mbox{M}$. 

Second line contains $N$ integers, which represent the elements of the array. 

$\mbox{M}$ queries follow. Each line contains a query of either type 1 or type 2 in the form $\textbf{type i j}$  

Constraints 

$1\leq N,M\leq10^5$ 

$1\leq A[i]\leq10^9$ 

$1\leq i\leq j\leq N$

Output Format

Print the absolute value i.e. $abs(A[1]-A[N])$ in the first line. 

Print elements of the resulting array in the second line. Each element should be seperated by a single space.

Sample Input
8 4
1 2 3 4 5 6 7 8
1 2 4
2 3 5
1 4 7
2 1 4

Sample Output
1
2 3 6 5 7 8 4 1

Explanation

Given array is $\{1,2,3,4,5,6,7,8\}$. 

After execution of query $1\:\text{}2\:\text{}4$, the array becomes $\{2,3,4,1,5,6,7,8\}$. 

After execution of query$2\:\text{}3\:\text{}5$, the array becomes $\{2,3,6,7,8,4,1,5\}$. 

After execution of query $\textbf{1}\:4\:7$, the array becomes $\{7,8,4,1,2,3,6,5\}$. 

After execution of query $2\:\text{}1\:\text{}4$, the array becomes $\{2,3,6,5,7,8,4,1\}$. 

Now $\left|A[1]-A[N]\right|$ is $|(2-1)|$ i.e. $1$ and the array is $23657841$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Tree queries


Solutions:
from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


import sys
import array
(N, M) = (int(a) for a in sys.stdin.readline().split())
AA = array.array('I', [int(a) for a in sys.stdin.readline().split()])
A = array.array('I', [a for a in range(N)])
for q in range(M):
	(typ, p1, p2) = [int(a) for a in sys.stdin.readline().split()]
	if typ == 1:
		A = A[p1 - 1:p2] + A[:p1 - 1] + A[p2:]
	elif typ == 2:
		A = A[:p1 - 1] + A[p2:] + A[p1 - 1:p2]
print('{}'.format(abs(AA[A[0]] - AA[A[N - 1]])))
print(' '.join((str(AA[A[a]]) for a in range(N))))
A = [(1, 8)]


from array import *
description = list(map(int, input().split(' ')))
the_array = list(map(int, input().split(' ')))
the_array = array('i', the_array)
for i in range(description[1]):
	comm = list(map(int, input().split(' ')))
	if comm[0] == 1:
		start_loc = comm[1] - 1
		end_loc = comm[2]
		move_set = the_array[start_loc:end_loc]
		the_array = move_set + the_array[:start_loc] + the_array[end_loc:]
	if comm[0] == 2:
		start_loc = comm[1] - 1
		end_loc = comm[2]
		move_set = the_array[start_loc:end_loc]
		the_array = the_array[:start_loc] + the_array[end_loc:] + move_set
print(abs(the_array[0] - the_array[-1]))
for i in range(len(the_array)):
	print(the_array[i], end=' ')


class Node:

	def __init__(self, value):
		self.val = value
		(self.left, self.right) = (None, None)
		(self.nLeftChildren, self.nRightChildren) = (0, 0)

def Build(arr):
	root = Node(arr[len(arr) // 2]) if len(arr) else None
	if len(arr) > 1:
		root.left = Build(arr[:len(arr) // 2])
		root.nLeftChildren = root.left.nLeftChildren + root.left.nRightChildren + 1
		if len(arr) > 2:
			root.right = Build(arr[len(arr) // 2 + 1:])
			root.nRightChildren = root.right.nLeftChildren + root.right.nRightChildren + 1
	return root

def InOrder(root):
	if root:
		InOrder(root.left)
		print(root.val, end=' ')
		InOrder(root.right)

def Find(root, index):
	if root.nLeftChildren > index:
		return Find(root.left, index)
	elif root.nLeftChildren < index:
		return Find(root.right, index - root.nLeftChildren - 1)
	else:
		return root

def Split(root, index):
	if root.nLeftChildren > index:
		(left, right) = Split(root.left, index)
		root.left = right
		root.nLeftChildren = right.nLeftChildren + right.nRightChildren + 1 if right else 0
		return (left, root)
	elif root.nLeftChildren < index:
		(left, right) = Split(root.right, index - root.nLeftChildren - 1)
		root.right = left
		root.nRightChildren = left.nLeftChildren + left.nRightChildren + 1 if left else 0
		return (root, right)
	else:
		left = root.left
		root.left = None
		root.nLeftChildren = 0
		return (left, root)

def Merge(leftRoot, rightRoot):
	if not leftRoot:
		return rightRoot
	elif not rightRoot:
		return leftRoot
	elif leftRoot.nRightChildren + max(rightRoot.nLeftChildren, rightRoot.nRightChildren) - leftRoot.nLeftChildren < rightRoot.nLeftChildren + max(leftRoot.nLeftChildren, leftRoot.nRightChildren) - rightRoot.nRightChildren:
		leftRoot.right = Merge(leftRoot.right, rightRoot)
		leftRoot.nRightChildren = leftRoot.right.nLeftChildren + leftRoot.right.nRightChildren + 1 if leftRoot.right else 0
		return leftRoot
	else:
		rightRoot.left = Merge(leftRoot, rightRoot.left)
		rightRoot.nLeftChildren = rightRoot.left.nLeftChildren + rightRoot.left.nRightChildren + 1 if rightRoot.left else 0
		return rightRoot
(N, M) = map(int, input().split())
treap = Build(list(map(int, input().split())))
for _ in range(M):
	(command, i, j) = map(int, input().split())
	(left, right) = Split(treap, i - 1)
	(mid, right) = Split(right, j - i + 1)
	treap = Merge(left, right)
	treap = Merge(mid, treap) if command == 1 else Merge(treap, mid)
print(abs(Find(treap, 0).val - Find(treap, N - 1).val))
InOrder(treap)
print('')


import random
import sys

class Node:

	def __init__(self, left, right, data):
		self.left = left
		self.right = right
		self.data = data
		self.size = 1
		if left is not None:
			self.size += left.size
		if right is not None:
			self.size += right.size

	def __str__(self):
		return '[data: ' + str(self.data) + '- size:' + str(self.size) + ']'

def size(node):
	if node is None:
		return 0
	return node.size

def update_size(node):
	if node is not None:
		node.size = 1 + size(node.left) + size(node.right)

def first(root):
	if root.left is not None:
		return first(root.left)
	else:
		return root

def last(root):
	if root.right is not None:
		return last(root.right)
	else:
		return root

def BuildTree(tab):
	if len(tab) == 0:
		return None
	if len(tab) == 1:
		return Node(None, None, tab[0])
	mid = len(tab) // 2
	return Node(BuildTree(tab[:mid]), BuildTree(tab[mid + 1:]), tab[mid])

def inOrder(root):
	if root is None:
		print('', end='')
	else:
		inOrder(root.left)
		print(str(root.data), end=' ')
		inOrder(root.right)

def split(root, key, add):
	if root is None:
		return (None, None)
	idx = add + size(root.left)
	if idx <= key:
		(l, r) = split(root.right, key, idx + 1)
		root.right = l
		update_size(root)
		return (root, r)
	else:
		(l, r) = split(root.left, key, add)
		root.left = r
		update_size(root)
		return (l, root)

def merge(l, r):
	if l is None:
		return r
	if r is None:
		return l
	if size(l.left) > size(r.right):
		l.right = merge(l.right, r)
		update_size(l)
		return l
	else:
		r.left = merge(l, r.left)
		update_size(r)
		return r
f = sys.stdin
s = f.readline().split()
N = int(s[0])
M = int(s[1])
A = [int(x) for x in f.readline().split()]
root = BuildTree(A)
for k in range(M):
	s = f.readline().split()
	op = s[0]
	i = int(s[1])
	j = int(s[2])
	if i > 1:
		(l, tmp) = split(root, i - 2, 0)
	else:
		(l, tmp) = (None, root)
	(m, r) = split(tmp, j - i, 0)
	if op == '1':
		root = merge(m, merge(l, r))
	elif op == '2':
		root = merge(merge(l, r), m)
	else:
		print('ERROR')
print(abs(last(root).data - first(root).data))
inOrder(root)


import random
import sys

class Treap:

	def __init__(self, value):
		self.value = value
		self.priority = random.random()
		self.size = 1
		self.left = None
		self.right = None

def merge(left, right):
	if left == None:
		return right
	if right == None:
		return left
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	else:
		right.size += left.size
		right.left = merge(left, right.left)
		return right

def split(treap, left, right):
	(middleTreap, rightTreap) = splitHelper(treap, right)
	(leftTreap, middleTreap) = splitHelper(middleTreap, left)
	return (leftTreap, middleTreap, rightTreap)

def splitHelper(treap, value):
	if value == 0 or not treap:
		return (None, treap)
	leftSize = treap.left.size if treap.left else 0
	if leftSize >= value:
		treap.size -= leftSize
		(l, r) = splitHelper(treap.left, value)
		treap.left = None
		return (l, merge(r, treap))
	else:
		treap.size -= treap.right.size if treap.right else 0
		(l, r) = splitHelper(treap.right, value - leftSize - 1)
		treap.right = None
		return (merge(treap, l), r)

def printTreapHelper(treap):
	if treap:
		printTreapHelper(treap.left)
		sys.stdout.write(str(treap.value) + ' ')
		printTreapHelper(treap.right)

def printTreap(treap):
	printTreapHelper(treap)
	print()

def getDiff(treap):
	stored = treap
	while stored.left:
		stored = stored.left
	left = stored.value
	stored = treap
	while stored.right:
		stored = stored.right
	return abs(left - stored.value)
(length, queries) = [int(i) for i in input().split()]
array = [int(i) for i in input().split()]
treap = Treap(array[0])
for elem in array[1:]:
	treap = merge(treap, Treap(elem))
for _ in range(queries):
	query = [int(i) for i in input().split()]
	(treapLeft, treapMiddle, treapRight) = split(treap, query[1] - 1, query[2])
	if query[0] == 1:
		treap = merge(merge(treapMiddle, treapLeft), treapRight)
	else:
		treap = merge(merge(treapLeft, treapRight), treapMiddle)
print(getDiff(treap))
printTreap(treap)


import sys, bisect, itertools, array

def log(*args):
	print(*args, file=sys.stderr)

class Arr:

	def __init__(self, v):
		self.v = array.array('I', v)

	def front(self, i, j):
		i -= 1
		n = j - i
		v = self.v
		if n < i:
			tmp = v[i:j]
			v[n:j] = v[:i]
			v[:n] = tmp
		else:
			tmp = v[:i]
			v[:n] = v[i:j]
			v[n:j] = tmp

	def back(self, i, j):
		i -= 1
		n = j - i
		v = self.v
		N = len(v) - j
		if n < N:
			tmp = v[i:j]
			v[i:-n] = v[j:]
			v[-n:] = tmp
		else:
			tmp = v[j:]
			v[-n:] = v[i:j]
			v[i:-n] = tmp

	def abs(self):
		return abs(self.v[0] - self.v[-1])

def main():
	(N, M) = (int(x) for x in input().split(' '))
	v = Arr([int(x) for x in input().split(' ')])
	lookup = {'1': v.front, '2': v.back}
	for _ in range(M):
		tokens = input().split(' ')
		lookup[tokens[0]](*(int(x) for x in tokens[1:]))
	print(v.abs())
	print(' '.join(map(str, v.v)))
main()


(sz, numops) = [int(n) for n in input().split()]
arr = [int(n) for n in input().split()]
str = ''.join((chr(n + 96) for n in arr))
for i in range(numops):
	inp = [int(n) for n in input().split()]
	start = inp[1]
	end = inp[2]
	if inp[0] == 1:
		if start > 1:
			str = str[start - 1:end] + str[0:start - 1] + str[end:]
		else:
			str = str[0:end] + str[end:]
	elif start > 1:
		str = str[0:start - 1] + str[end:] + str[start - 1:end]
	else:
		str = str[end:] + str[0:end]
start = ord(str[0]) - 97
end = ord(str[-1]) - 97
print(abs(start - end))
for i in range(sz):
	print(ord(str[i]) - 96, end=' ')


import struct
(N, M) = map(int, input().split())
arr = []
arr = [int(k) for k in input().split()]
arr = struct.pack('%si' % N, *arr)
for _ in range(M):
	query = list(map(int, input().split()))
	i = query[1]
	j = query[2]
	if query[0] == 1:
		arr = arr[4 * (i - 1):4 * j] + arr[:4 * (i - 1)] + arr[4 * j:]
	else:
		arr = arr[:4 * (i - 1)] + arr[4 * j:] + arr[4 * (i - 1):4 * j]
arr = struct.unpack('i' * N, arr)
print(abs(arr[0] - arr[-1]))
print(*arr, sep=' ')


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array

def solve():
	(n, m) = map(int, input().split())
	arr = array('L', map(int, input().split()))
	for _ in range(m):
		(t, i, j) = map(int, input().split())
		if t == 1:
			(arr[:j - i + 1], arr[j - i + 1:j]) = (arr[i - 1:j], arr[:i - 1])
		elif t == 2:
			(arr[i - 1:n + i - j - 1], arr[n + i - j - 1:]) = (arr[j:], arr[i - 1:j])
	val = abs(int(arr[0]) - int(arr[-1]))
	print(val)
	print(' '.join(map(str, arr)))
solve()


import array
nm = input().split()
n = int(nm[0])
m = int(nm[1])
a = array.array('I', list(map(int, input().rstrip().split())))
for q in range(m):
	tij = input().split()
	t = int(tij[0])
	i = int(tij[1]) - 1
	j = int(tij[2])
	if t == 1:
		a = a[i:j] + a[0:i] + a[j:]
	else:
		a = a[0:i] + a[j:] + a[i:j]
print(abs(a[0] - a[-1]))
for i in range(len(a)):
	print(a[i], end=' ')


from array import array
import sys

def main():
	(n, m) = map(int, sys.stdin.readline().split())
	inarray = array('L')
	inarray.extend(map(int, sys.stdin.readline().split()))
	view = memoryview(inarray)
	for _ in range(m):
		(qtype, from_, to) = map(int, sys.stdin.readline().split())
		from_ = from_ - 1
		if qtype == 1:
			buf = inarray[from_:to]
			view[to - from_:to] = view[:from_]
			view[:to - from_] = buf
		else:
			buf = inarray[from_:to]
			view[from_:-(to - from_)] = view[to:]
			view[-(to - from_):] = buf
	print(abs(inarray[0] - inarray[-1]))
	print(' '.join(map(str, inarray)))
main()


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


import random

class Node:
	__slots__ = ['val', 'left', 'right', 'priority', 'cnt']

	def __init__(self, val, cnt):
		self.val = val
		self.left = None
		self.right = None
		self.priority = random.randint(1, 2 ** 64 - 1)
		self.cnt = cnt

class Treap:

	@staticmethod
	def from_array(arr):
		mid = len(arr) // 2
		node = Node(arr[mid], len(arr))
		if len(arr) == 1:
			return node
		if mid > 0:
			node.left = Treap.from_array(arr[:mid])
		if mid < len(arr) - 1:
			node.right = Treap.from_array(arr[mid + 1:])
		Treap.heapify(node)
		return node

	@staticmethod
	def heapify(node):
		max_node = node
		if node.left is not None and node.left.priority > node.priority:
			max_node = node.left
		if node.right is not None and node.right.priority > max_node.priority:
			max_node = node.right
		if max_node is node:
			return
		(node.priority, max_node.priority) = (max_node.priority, node.priority)
		Treap.heapify(max_node)

	@staticmethod
	def order(node):
		if node.left is not None:
			Treap.order(node.left)
		print(node.val, node.cnt)
		if node.right is not None:
			Treap.order(node.right)

	@staticmethod
	def split(node, k, add=0):
		if node is None:
			return (None, None)
		node_key = add
		if node.left is not None:
			node_key += node.left.cnt
		if k <= node_key:
			(left, node.left) = Treap.split(node.left, k, add)
			node.cnt = Treap.cnt(node)
			return (left, node)
		(node.right, right) = Treap.split(node.right, k, node_key + 1)
		node.cnt = Treap.cnt(node)
		return (node, right)

	@staticmethod
	def merge(node1, node2):
		if node1 is None:
			return node2
		if node2 is None:
			return node1
		if node1.priority > node2.priority:
			node1.right = Treap.merge(node1.right, node2)
			node1.cnt = Treap.cnt(node1)
			return node1
		node2.left = Treap.merge(node1, node2.left)
		node2.cnt = Treap.cnt(node2)
		return node2

	@staticmethod
	def cnt(node):
		cnt = 1
		if node.left is not None:
			cnt += node.left.cnt
		if node.right is not None:
			cnt += node.right.cnt
		return cnt

	@staticmethod
	def iter(node):
		if node.left is not None:
			yield from Treap.iter(node.left)
		yield node.val
		if node.right is not None:
			yield from Treap.iter(node.right)

def main(arr, queries):
	for query in queries:
		if query[0] == 1:
			pass
		elif query[0] == 2:
			pass
(n, m) = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
root = Treap.from_array(arr)
for _ in range(m):
	query = list(map(int, input().split(' ')))
	l = query[1]
	r = query[2]
	if query[0] == 1:
		(mid, leftright) = Treap.split(root, l - 1)
		(left, right) = Treap.split(leftright, r - l + 1)
		root = Treap.merge(Treap.merge(left, mid), right)
	elif query[0] == 2:
		(left, midright) = Treap.split(root, l - 1)
		(right, mid) = Treap.split(midright, r - l + 1)
		root = Treap.merge(Treap.merge(left, mid), right)
new_arr = list(Treap.iter(root))
print(abs(new_arr[0] - new_arr[-1]))
print(' '.join(map(str, new_arr)))


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, m) = map(int, input().split(' '))
s = array('L', map(int, input().split(' ')))
while m:
	(a, b, c) = map(int, input().split(' '))
	if a == 1:
		i = b - 1
		j = c - i
		(s[:j], s[j:c]) = (s[i:c], s[:i])
	else:
		i = b - 1
		j = i + n - c
		(s[i:j], s[j:]) = (s[c:], s[i:c])
	m -= 1
print(abs(s[0] - s[-1]))
print(*s)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, q) = map(int, input().split())
l = array('L', map(int, input().split()))
for i in range(q):
	(t, i, j) = map(int, input().split())
	if t == 1:
		astart = i - 1
		aend = j - astart
		(l[:aend], l[aend:j]) = (l[astart:j], l[:astart])
	else:
		astart = i - 1
		aend = astart + n - j
		(l[astart:aend], l[aend:]) = (l[j:], l[astart:j])
print(abs(l[0] - l[-1]))
print(*l)


(sz, numops) = [int(n) for n in input().split()]
arr = [int(n) for n in input().split()]
str = ''.join((chr(n + 96) for n in arr))
for i in range(numops):
	inp = [int(n) for n in input().split()]
	start = inp[1]
	end = inp[2]
	if inp[0] == 1:
		if start > 1:
			str = str[start - 1:end] + str[0:start - 1] + str[end:]
		else:
			str = str[0:end] + str[end:]
	elif start > 1:
		str = str[0:start - 1] + str[end:] + str[start - 1:end]
	else:
		str = str[end:] + str[0:end]
start = ord(str[0]) - 96
end = ord(str[-1]) - 96
print(abs(start - end))
for i in range(sz):
	print(ord(str[i]) - 96, end=' ')


(sz, numops) = [int(n) for n in input().split()]
arr = [int(n) for n in input().split()]
str = ''.join((chr(n + 96) for n in arr))
for i in range(numops):
	inp = [int(n) for n in input().split()]
	start = inp[1]
	end = inp[2]
	if inp[0] == 1:
		if start > 1:
			str = str[start - 1:end] + str[0:start - 1] + str[end:]
		else:
			str = str[0:end] + str[end:]
	elif start > 1:
		str = str[0:start - 1] + str[end:] + str[start - 1:end]
	else:
		str = str[end:] + str[0:end]
start = ord(str[0]) - 96
end = ord(str[-1]) - 96
print(abs(start - end))
for i in range(sz):
	print(ord(str[i]) - 96, end=' ')


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data_array = array('L', map(int, input().split()))
assert len(data_array) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		a1 = i - 1
		a2 = j - a1
		(data_array[:a2], data_array[a2:j]) = (data_array[a1:j], data_array[:a1])
	else:
		a1 = i - 1
		a2 = a1 + n - j
		(data_array[a1:a2], data_array[a2:]) = (data_array[j:], data_array[a1:j])
print(abs(data_array[0] - data_array[-1]))
print(*data_array)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from random import random

class Treap:

	def __init__(self, val, priority):
		self.val = val
		self.priority = priority
		self.size = 1
		self.right = None
		self.left = None

	def __getitem__(self, index):
		if self.left and index <= self.left.size:
			return self.left[index]
		index -= self.left.size if self.left else 0
		if index == 1:
			return self.val
		return self.right[index - 1]

	def __str__(self):
		res = str(self.left) if self.left else ''
		res += str(self.val) + ' '
		res += str(self.right) if self.right else ''
		return res

def merge(left, right):
	if not (left and right):
		return left or right
	if left.priority > right.priority:
		left.size += right.size
		left.right = merge(left.right, right)
		return left
	right.size += left.size
	right.left = merge(left, right.left)
	return right

def split(t, index):
	if not index:
		return (None, t)
	if not t:
		return (None, None)
	if index == t.size:
		return (t, None)
	if t.left and t.left.size >= index:
		(res, t.left) = split(t.left, index)
		t.size -= res.size
		return (res, t)
	index -= t.left.size if t.left else 0
	if index == 1:
		temp = t.right
		t.right = None
		t.size -= temp.size
		return (t, temp)
	(t.right, leftover) = split(t.right, index - 1)
	t.size -= leftover.size
	return (t, leftover)

def handle(t, key, start, end):
	start -= 1
	(left, t) = split(t, start)
	(t, right) = split(t, end - start)
	res = merge(left, right)
	if key == 1:
		res = merge(t, res)
	else:
		res = merge(res, t)
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
priorities = [5, 7, 6, 9, 10, 1, 0, 3]
t = Treap(a[0], random())
for i in a[1:]:
	t = merge(t, Treap(i, random()))
for _ in range(m):
	t = handle(t, *map(int, input().split()))
print(abs(t[1] - t[n]))
print(t)


from collections import deque
from itertools import chain
from math import ceil, sqrt
from sys import stderr

def read_ints():
	return map(int, input().split())

def append(Q, X):
	if Q and len(Q[-1]) < S and (len(X) < S):
		Q[-1] += X
	else:
		Q.append(X)

def prepend(Q, X):
	if Q and len(Q[0]) < S and (len(X) < S):
		X += Q[0]
		Q[0] = X
	else:
		Q.appendleft(X)

def rotateleft(Q, n, R):
	while n > 0:
		a = Q.popleft()
		m = len(a)
		if n < m:
			prepend(Q, a[n:])
			del a[n:]
			append(R, a)
			break
		R.append(a)
		n -= m

def rotateright(Q, n, R):
	while n > 0:
		a = Q.pop()
		m = len(a)
		if n < m:
			prepend(R, a[-n:])
			del a[-n:]
			append(Q, a)
			break
		R.appendleft(a)
		n -= m
(N, M) = read_ints()
S = int(ceil(sqrt(N)))
A = list(read_ints())
B = deque()
for i in range(0, N, S):
	B.append(A[i:i + S])
for _ in range(M):
	(c, i, j) = read_ints()
	splice = deque()
	if i <= N - j:
		rotateleft(B, i - 1, B)
		rotateleft(B, j - i + 1, splice)
		rotateright(B, i - 1, B)
	else:
		rotateright(B, N - j, B)
		rotateright(B, j - i + 1, splice)
		rotateleft(B, N - j, B)
	if c == 1:
		B.extendleft(reversed(splice))
	elif c == 2:
		B.extend(splice)
R = list(chain.from_iterable(B))
print(abs(R[0] - R[-1]))
print(' '.join(map(str, R)))


from array import array
(n, q) = map(int, input().split())
d = array('L', map(int, input().split()))
assert len(d) == n
for m in range(q):
	(t, i, j) = map(int, input().split())
	if t == 1:
		a1 = i - 1
		a2 = j - a1
		(d[:a2], d[a2:j]) = (d[a1:j], d[:a1])
	else:
		a1 = i - 1
		a2 = a1 + n - j
		(d[a1:a2], d[a2:]) = (d[j:], d[a1:j])
print(abs(d[0] - d[-1]))
print(*d)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		strVal = i - 1
		totLne = j - i + 1
		(data[:totLne], data[totLne:j]) = (data[strVal:j], data[:strVal])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, q) = map(int, input().strip().split())
arr = array('L', map(int, input().strip().split()))
assert len(arr) == n
for i in range(q):
	(t, x, y) = map(int, input().strip().split())
	if t == 1:
		r1 = x - 1
		r2 = y - r1
		(arr[:r2], arr[r2:y]) = (arr[r1:y], arr[:r1])
	else:
		r1 = x - 1
		r2 = r1 + n - y
		(arr[r1:r2], arr[r2:]) = (arr[y:], arr[r1:y])
print(abs(arr[0] - arr[-1]))
print(*arr)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		a1 = i - 1
		a2 = j - a1
		(data[:a2], data[a2:j]) = (data[a1:j], data[:a1])
	else:
		a1 = i - 1
		a2 = a1 + n - j
		(data[a1:a2], data[a2:]) = (data[j:], data[a1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)


from array import array
(n, n_queries) = map(int, input().split())
data = array('L', map(int, input().split()))
assert len(data) == n
for m in range(n_queries):
	(t, i, j) = map(int, input().split())
	if t == 1:
		aux1 = i - 1
		aux2 = j - aux1
		(data[:aux2], data[aux2:j]) = (data[aux1:j], data[:aux1])
	else:
		aux1 = i - 1
		aux2 = aux1 + n - j
		(data[aux1:aux2], data[aux2:]) = (data[j:], data[aux1:j])
print(abs(data[0] - data[-1]))
print(*data)