#include <iostream>

template <typename T>
struct Node {
	T value;
	Node<T>* next;

	Node(T value, Node<T>* next = nullptr) : value(value), next(next) {}
};

template <typename T, typename U>
struct Pair {
	T left;
	U right;

	Pair(T left, U right) : left(left), right(right) {}
};

#define PII Pair<int, int>
#define NPII Node<Pair<int, int>*>

template <typename T>
void reverseSublist(Node<T>*& list, int start, int end) {
	Node<T>* prev = nullptr; // element before first in range
	Node<T>* iter = list; // first element in range
	while (start > 0) {
		prev = iter;
		iter = iter->next;
		start--;
		end--;
	}
	Node<T>* eter = iter; // last element in range
	Node<T>* next = nullptr; // element after last in range
	for (int i = 0; i < end; i++) {
		eter = eter->next;
		next = eter->next;
	}

	prev->next = eter;
	Node<T>* last;
	Node<T>* prevLast;
	while (end > 0) {
		prevLast = iter;
		last = iter->next;
		for (int i = 1; i < end; i++) {
			prevLast = prevLast->next;
			last = last->next;
		}
		last->next = prevLast;
		end--;
	}
	prevLast->next = next;
}

template <typename T>
void reverseSublists(Node<T>*& list, NPII* intervals) {
	while (intervals != nullptr) {
		reverseSublist(list, intervals->value->left, intervals->value->right);
		intervals = intervals->next;
	}
}

template <typename T>
void print(Node<T>* list) {
	while (list != nullptr) {
		std::cout << list->value << " ";
		list = list->next;
	}
	std::cout << std::endl;
}

int main() {
	NPII* intervals = new NPII(new PII(1, 3), new NPII(new PII(2, 5), new NPII(new PII(5, 6))));
	Node<int>* list = new Node<int>(11, new Node<int>(4, new Node<int>(3, new Node<int>(7, new Node<int>(13, new Node<int>(4, new Node<int>(5)))))));

	print(list);
	reverseSublists(list, intervals);
	print(list);

	NPII* temp = nullptr;
	while (intervals != nullptr) {
		delete intervals->value;
		temp = intervals->next;
		delete intervals;
		intervals = temp;
	}

	Node<int>* temp1 = nullptr;
	while (list != nullptr) {
		temp1 = list->next;
		delete list;
		list = temp1;
	}
}