You are given a sequence $a_1,a_2,\ldots,a_n$. The task is to perform the following queries on it:

Type 1. Given two integers $\boldsymbol{l}$ and $\textbf{r}$ $(1\leq l\lt r\leq n;r-l+1\ is even)$. Reorder the elements of the sequence in such a way (changed part of the sequence is in brackets):
$a_1,a_2,\ldots,a_n\rightarrow a_1,a_2,\ldots,a_{l-2},a_{l-1},\left[a_{l+1},a_l,a_{l+3},a_{l+2},\ldots,a_{r},a_{r-1}\right],a_{r+1},a_{r+2},\ldots,a_{n}$
That is swap the first two elements of segment $[l,r]$, the second two elements, and so on.

Type 2. Given two integers $\boldsymbol{l}$ and $\textbf{r}$, print the value of sum $\sum\limits_{i=l}^{r}a_{i}$.

Input Format  

The first line contains two integers $n$ and $\textit{q}$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, denoting initial sequence.

Each of the next $\textit{q}$ lines contains three integers $tp_i,l_i,r_i$, where $t p_i$ denotes the type of the query, and $l_i,r_i$ are parameters of the query. It's guaranteed that for a first-type query $(r-l+1)$ will be even.  

Constraints 

$2\leq n\leq2\times10^5$ 

$1\leq q\leq2\times10^5$ 

$1\leq a_i\leq10^6$ 

$1\leq t p_i\leq2$ 

$1\leq l_i\leq r_i\leq n$

Output Format

For each query of the second type print the required sum.

Sample Input

6 4
1 2 3 4 5 6
1 2 5
2 2 3
2 3 4
2 4 5

Example Output

5
7
9

Explanation

After the first query the sequence becomes [1, 3, 2, 5, 4, 6].

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))


def main():
	(n, q) = readints()
	a = readints()
	assert len(a) == n
	for _ in range(q):
		(tp, lf, rt) = [f - 1 for f in readints()]
		if tp == 0:
			(a[lf:rt + 1:2], a[lf + 1:rt + 1:2]) = (a[lf + 1:rt + 1:2], a[lf:rt + 1:2])
		else:
			assert tp == 1
			print(sum(a[lf:rt + 1]))

def readints():
	return list(map(int, input().split()))
main()


(N, Q) = input().split()
N = int(N)
Q = int(Q)
a = list()
t = l = r = int()
a = input().split()

def typ2(a, l, r):
	suma = 0
	for x in range(l - 1, r):
		suma += a[x]
	print(suma)

def typ1(a, l, r):
	tmp = 0
	for x in range(l - 1, r, 2):
		tmp = a[x]
		a[x] = a[x + 1]
		a[x + 1] = tmp
for x in range(len(a)):
	a[x] = int(a[x])
while Q > 0:
	(t, l, r) = input().split()
	if t == '1':
		typ1(a, int(l), int(r))
	else:
		typ2(a, int(l), int(r))
	Q -= 1


(size, times) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]

def arrange(arr, l, r):
	l -= 1
	r -= 1
	for num in range(l, r, 2):
		(arr[num], arr[num + 1]) = (arr[num + 1], arr[num])
	return arr
for _ in range(times):
	(tipo, l, r) = [int(x) for x in input().split()]
	if tipo == 1:
		arr = arrange(arr, l, r)
	if tipo == 2:
		print(sum(arr[l - 1:r]))


def main():
	(n, q) = [int(x) for x in input().split()]
	alist = [int(x) for x in input().split()]
	for i in range(q):
		(t, l, r) = [int(x) for x in input().split()]
		if t == 2:
			print(sum(alist[l - 1:r]))
		if t == 1:
			for i in range(l - 1, r, 2):
				(alist[i], alist[i + 1]) = (alist[i + 1], alist[i])
main()


line = input('')
line = list(map(int, line.split()))
N = line[0]
Q = line[1]
line = input('')
seq = list(map(int, line.split()))
for q in range(0, Q):
	line = input('')
	line = list(map(int, line.split()))
	T = line[0]
	L = line[1]
	R = line[2]
	if T == 1:
		a = seq[L - 1:R:2]
		b = seq[L:R:2]
		c = [item for sublist in zip(b, a) for item in sublist]
		seq = seq[:L - 1] + c + seq[R:]
	if T == 2:
		print(sum(seq[L - 1:R]))


(N, Q) = map(int, input().split())
seq = [0] + list(map(int, input().split()))

def type1query(l, r):
	for i in range(l, r + 1, 2):
		(seq[i], seq[i + 1]) = (seq[i + 1], seq[i])
for i in range(Q):
	(type, l, r) = map(int, input().split())
	if type == 1:
		type1query(l, r)
	else:
		print(sum(seq[l:r + 1]))


def queryone(s, l, r):
	sub = s[l:r + 1]
	evens = sub[::2]
	odds = sub[1::2]
	newS = []
	for (i, j) in zip(evens, odds):
		newS += [j, i]
	newS = s[0:l] + newS + s[r + 1:len(s)]
	return newS

def querytwo(s, l, r):
	return sum(s[l:r + 1])

def toInt(s):
	for (i, n) in enumerate(s):
		s[i] = int(n)
	return s
q = int(input().split()[1])
sequence = toInt(input().split())
toPrint = []
for _ in range(q):
	query = toInt(input().split())
	querytype = query[0]
	(l, r) = (query[1] - 1, query[2] - 1)
	if querytype == 1:
		sequence = queryone(sequence, l, r)
	elif querytype == 2:
		toPrint.append(querytwo(sequence, l, r))
for p in toPrint:
	print(p)


def swap(numbers, l, r):
	for i in range(l - 1, r, 2):
		(numbers[i], numbers[i + 1]) = (numbers[i + 1], numbers[i])
	return numbers
(nNumbers, nQuery) = list(map(int, input().split()))
numbers = list(map(int, input().split()))
for _ in range(nQuery):
	(tp, l, r) = list(map(int, input().split()))
	if tp == 1:
		numbers = swap(numbers, l, r)
	if tp == 2:
		print(sum(numbers[l - 1:r]))


from array import array
(n, q) = map(int, input().split())
data = array('l', [0])
data.extend(map(int, input().split()))
for _ in range(q):
	(t, l, r) = map(int, input().split())
	if t == 1:
		(data[l:r:2], data[l + 1:r + 1:2]) = (data[l + 1:r + 1:2], data[l:r:2])
	elif t == 2:
		print(sum(data[l:r + 1]))


(n, q) = map(int, str(input()).split(' '))
numbers = list(map(int, str(input()).split(' ')))
for i in range(0, q):
	(type, l, r) = map(int, str(input()).split(' '))
	if type == 1:
		for j in range(l - 1, r, 2):
			(numbers[j], numbers[j + 1]) = (numbers[j + 1], numbers[j])
	if type == 2:
		print(sum(numbers[l - 1:r]))


import array
(N, Q) = map(int, input().strip().split())
seqArr = array.array('i', map(int, input().strip().split()))

def totalSum(arr, start, end):
	total = 0
	for i in range(start, end):
		total += arr[i]
	return total

def swap(arr, start, end):
	for i in range(start, end, 2):
		tmp = arr[i]
		arr[i] = arr[i + 1]
		arr[i + 1] = tmp
delayedSwaps = []
for q in range(Q):
	(type, left, right) = map(int, input().strip().split())
	left -= 1
	if type == 1:
		i = 0
		while True:
			if i >= len(delayedSwaps):
				delayedSwaps.append([left, right])
				break
			if delayedSwaps[i][0] > right:
				delayedSwaps.insert(i, [left, right])
				break
			elif delayedSwaps[i][1] <= left:
				i += 1
				continue
			elif left % 2 == delayedSwaps[i][0] % 2:
				if left < delayedSwaps[i][0]:
					newStart = delayedSwaps[i][0]
					delayedSwaps.insert(i, [left, delayedSwaps[i][0]])
					left = newStart
					i += 1
					continue
				elif left == delayedSwaps[i][0]:
					if delayedSwaps[i][1] < right:
						left = delayedSwaps[i][1]
						del delayedSwaps[i]
						continue
					elif delayedSwaps[i][1] == right:
						del delayedSwaps[i]
						break
					else:
						delayedSwaps[i][0] = right
						break
				elif delayedSwaps[i][1] < right:
					newStart = delayedSwaps[i][1]
					delayedSwaps[i][1] = left
					left = newStart
					i += 1
					continue
				elif delayedSwaps[i][1] == right:
					delayedSwaps[i][1] = left
					break
				else:
					newEnd = delayedSwaps[i][1]
					newStart = right
					delayedSwaps[i][1] = left
					i += 1
					delayedSwaps.insert(i, [newStart, newEnd])
					break
			else:
				swap(seqArr, delayedSwaps[i][0], delayedSwaps[i][1])
				del delayedSwaps[i]
				continue
	else:
		if len(delayedSwaps) > 0:
			i = 0
			while i < len(delayedSwaps):
				if delayedSwaps[i][0] > right:
					i += 1
				elif delayedSwaps[i][1] <= left:
					i += 1
				elif delayedSwaps[i][0] >= left and delayedSwaps[i][1] <= right:
					i += 1
				else:
					swap(seqArr, delayedSwaps[i][0], delayedSwaps[i][1])
					del delayedSwaps[i]
		print(totalSum(seqArr, left, right))


def swap_sum(a, l, r):
	for i in range(l, r, 2):
		a[i] = a[i + 1] - a[i] + a[i - 1]

def print_sum(a, l, r):
	return a[r] - a[l - 1]
(n, q) = map(int, str(input()).split(' '))
arr = [0] + list(map(int, str(input()).split(' ')))
arr_sum = [x for x in arr]
for index in range(1, len(arr)):
	arr_sum[index] += arr_sum[index - 1]
for q_i in range(q):
	(tp, l, r) = map(int, str(input()).split(' '))
	if tp == 1:
		swap_sum(arr_sum, l, r)
	else:
		print(print_sum(arr_sum, l, r))


def calculate_type_1(data, l, r):
	step = 0
	for x in range(l, r + 1):
		if not step % 2:
			temp = data[x]
			data[x] = data[x - 1]
			data[x - 1] = temp
		step += 1

def calculate_type_2(data, l, r):
	return sum(data[l - 1:r])
(n, q) = (int(x) for x in input().split())
data_arr = [int(x) for x in input().split()]
for _ in range(q):
	(oper, left, right) = (int(x) for x in input().split())
	if oper == 1:
		calculate_type_1(data_arr, left, right)
	else:
		print(calculate_type_2(data_arr, left, right))


(n, q) = input().split()
q = int(q)
arr = [int(d) for d in input().strip().split()]
for i in range(q):
	(t, l, r) = input().split()
	l = int(l)
	r = int(r)
	if t == '1':
		for j in range(l - 1, r, 2):
			(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
	else:
		ans = 0
		ans = sum(arr[l - 1:r])
		print(ans)


import os
import sys

def solve(a, queries, q):
	for i in range(q):
		if queries[i][0] == 1:
			for j in range(queries[i][1] - 1, queries[i][2], 2):
				(a[j], a[j + 1]) = (a[j + 1], a[j])
		elif queries[i][0] == 2:
			sum = 0
			for j in range(queries[i][1] - 1, queries[i][2]):
				sum = sum + a[j]
			print(sum)
nq = input().split()
n = int(nq[0])
q = int(nq[1])
a = list(map(int, input().rstrip().split()))
queries = []
for _ in range(q):
	queries.append(list(map(int, input().rstrip().split())))
result = solve(a, queries, q)


import os
import sys

def solve(a, queries):
	for i in range(q):
		qtype = queries[i][0]
		l = queries[i][1]
		r = queries[i][2]
		if qtype == 1:
			for i in range(l - 1, r, 2):
				temp = a[i]
				a[i] = a[i + 1]
				a[i + 1] = temp
		else:
			summ = 0
			for i in range(l - 1, r):
				summ = summ + a[i]
			print(summ)
nq = input().split()
n = int(nq[0])
q = int(nq[1])
a = list(map(int, input().rstrip().split()))
queries = []
for _ in range(q):
	queries.append(list(map(int, input().rstrip().split())))
solve(a, queries)


(n, m) = map(int, input().split())
seq = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(m)]
for (q, l, r) in queries:
	if q == 1:
		for i in range(l, r, 2):
			(seq[i], seq[i - 1]) = (seq[i - 1], seq[i])
	elif q == 2:
		print(sum(seq[l - 1:r]))


def _tp1_(l, r, a):
	for i in range(l - 1, r, 2):
		(a[i], a[i + 1]) = (a[i + 1], a[i])
	return a

def _tp2_(l, r, a):
	summ = 0
	for i in range(l - 1, r):
		summ += a[i]
	print(summ)
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(q):
	(tp, l, r) = map(int, input().split())
	if tp == 1:
		_tp1_(l, r, a)
	elif tp == 2:
		_tp2_(l, r, a)


(N, Q) = input().split()
N = int(N)
Q = int(Q)
a = list()
t = l = r = int()
a = input().split()

def typ2(a, l, r):
	suma = 0
	for x in range(l - 1, r):
		suma += a[x]
	print(suma)

def typ1(a, l, r):
	tmp = 0
	for x in range(l - 1, r, 2):
		tmp = a[x]
		a[x] = a[x + 1]
		a[x + 1] = tmp
for x in range(len(a)):
	a[x] = int(a[x])
while Q > 0:
	(t, l, r) = input().split()
	if t == '1':
		typ1(a, int(l), int(r))
	else:
		typ2(a, int(l), int(r))
	Q -= 1


def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))


def main():
	(n, q) = readints()
	a = readints()
	assert len(a) == n
	for _ in range(q):
		(tp, lf, rt) = [f - 1 for f in readints()]
		if tp == 0:
			(a[lf:rt + 1:2], a[lf + 1:rt + 1:2]) = (a[lf + 1:rt + 1:2], a[lf:rt + 1:2])
		else:
			assert tp == 1
			print(sum(a[lf:rt + 1]))

def readints():
	return list(map(int, input().split()))
main()


(m, n) = input().split()
l = [int(i) for i in input().split()]
for i in range(int(n)):
	a = input().strip().split()
	if a[0] == '1':
		for k in range(int(a[1]), int(a[2]) + 1, 2):
			(l[k - 1], l[k]) = (l[k], l[k - 1])
	if a[0] == '2':
		print(sum(l[int(a[1]) - 1:int(a[2])]))


s = list(map(int, input().split()))
k = list(map(int, input().split()))
kl = len(k)
for i in range(0, s[1]):
	i = list(map(int, input().split()))
	if i[0] == 1:
		h = k[i[1] - 1:i[2]]
		h1 = len(h)
		for j in range(0, h1, 2):
			a = h[j]
			h[j] = h[j + 1]
			h[j + 1] = a
		k1 = k[0:i[1] - 1]
		k2 = k[i[2]:kl]
		k = k1 + h + k2
	else:
		f = k[i[1] - 1:i[2]]
		print(sum(f))


import os
import sys
nq = input().split()
n = int(nq[0])
q = int(nq[1])
a = list(map(int, input().rstrip().split()))
queries = []
for _ in range(q):
	qu = list(map(int, input().rstrip().split()))
	if qu[0] == 1:
		for i in range(qu[1] - 1, qu[2], 2):
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	else:
		print(sum(a[qu[1] - 1:qu[2]]))


(N, Q) = input().split()
N = int(N)
Q = int(Q)
a = list()
t = l = r = int()
a = input().split()

def typ2(a, l, r):
	suma = 0
	for x in range(l - 1, r):
		suma += a[x]
	print(suma)

def typ1(a, l, r):
	tmp = 0
	for x in range(l - 1, r, 2):
		tmp = a[x]
		a[x] = a[x + 1]
		a[x + 1] = tmp
for x in range(len(a)):
	a[x] = int(a[x])
while Q > 0:
	(t, l, r) = input().split()
	if t == '1':
		typ1(a, int(l), int(r))
	else:
		typ2(a, int(l), int(r))
	Q -= 1


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
	(t, l, r) = map(int, input().split())
	l -= 1
	if t == 1:
		for i in range(l, r, 2):
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	else:
		print(sum(a[l:r]))


def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))


def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))


def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))


import math
import os
import random
import re
import sys

def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))


def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))


def read_numbers():
	return [int(i) for i in input().split(' ')]

def swap_numbers(l, r, numbers):
	sub = numbers[l:r]
	for i in range(0, r - l, 2):
		l1 = sub[i]
		r1 = sub[i + 1]
		sub[i + 1] = l1
		sub[i] = r1
	return sub
(n, q) = read_numbers()
numbers = read_numbers()
results = []
for x in range(q):
	(t, l, r) = read_numbers()
	l -= 1
	if t == 1:
		numbers[l:r] = swap_numbers(l, r, numbers)
	else:
		results.append(str(sum(numbers[l:r])))
print('\n'.join(results))