#include <stdio.h>
#include <algorithm>
#include "kollib.h"
#include "message.h"

struct Student
{
	int id;
	int pos;
};

int nodeId;
int masterId;
int numNodes;

int numOfStudents;
int n;
Student* students;

bool sortStudents(const Student& a, const Student& b)
{
	return a.id < b.id;
}


int search(int id)
{
	int from = 0;
	int to = n - 1;
	
	while (from <= to)
	{
		int mid = (from + to) / 2;
		if (students[mid].id == id)
			return students[mid].pos;
		else if (students[mid].id < id)
		{
			from = mid + 1;
		}
		else
		{
			to = mid - 1;
		}
	}
	return -1;
}

void processQuery(int query)
{
	int nextNode = (nodeId + 1) % numNodes;
	int from = QueryFrom(query);
	int to = QueryTo(query);
	
	int fromPos = search(from);
	int toPos = search(to);
	if (fromPos != -1 && toPos != -1)
	{
		int total = fromPos < toPos ? toPos - fromPos : fromPos - toPos;
		PutChar(masterId, 4);
		PutInt(masterId, query);
		PutInt(masterId, total);
		Send(masterId);
	}
	else if (fromPos != -1 || toPos != -1)
	{
		int total = fromPos != -1 ? n - fromPos : n - toPos;
		
		PutChar(nextNode, fromPos != -1 ? 1 : 2);
		PutInt(nextNode, query);
		PutInt(nextNode, total);
		Send(nextNode);
	}
	else
	{
		PutChar(nextNode, 3);
		PutInt(nextNode, query);
		Send(nextNode);
	}
}

void processOwnQuery()
{
	int nquery = NumberOfQueries() / numNodes;
	int mod = NumberOfQueries() % numNodes;
	if (nodeId < mod)
		nquery++;
	
	for (int i = 0; i < nquery; i++)
	{
		int query = i * numNodes + nodeId + 1;
		processQuery(query);
	}
}

void handleQuery(int sender, char mode)
{
	int query = GetInt(sender);
	int total = GetInt(sender);
	
	int second = (mode == 1 ? QueryTo(query) : QueryFrom(query));
	int secPos = search(second);
	if (secPos == -1)
	{
		int nextNode = (nodeId + 1) % numNodes;
		
		PutChar(nextNode, mode);
		PutInt(nextNode, query);
		PutInt(nextNode, total + n);
		Send(nextNode);
	}
	else
	{
		PutChar(masterId, 4);
		PutInt(masterId, query);
		PutInt(masterId, total + secPos);
		Send(masterId);
	}
}

void readStudents(int current, int last)
{
	students[0].id = current;
	students[0].pos = 0;
	for (int i = 0; i < n; i++)
	{
		int first = FirstNeighbor(students[i].id);
		int second = SecondNeighbor(students[i].id);
		int next = first == last ? second : first;
		if (i == n - 1)
		{
			if (nodeId < (numNodes / 2 - 1))
			{
				PutChar(nodeId + 1, 0);
				PutInt(nodeId + 1, next);
				PutInt(nodeId + 1, students[i].id);
				Send(nodeId + 1);
			}
		}
		else
		{
			students[i + 1].id = next;
			students[i + 1].pos = i + 1;
		}
		last = students[i].id;
	}
	
	std::sort(students, students + n, sortStudents);
}

void readStudentsBackward(int current, int last)
{
	students[n - 1].id = current;
	students[n - 1].pos = n - 1;
	for (int i = n - 1; i >= 0; i--)
	{
		int first = FirstNeighbor(students[i].id);
		int second = SecondNeighbor(students[i].id);
		int next = first == last ? second : first;
		if (i == 0)
		{
			if (nodeId > numNodes / 2)
			{
				PutChar(nodeId - 1, 0);
				PutInt(nodeId - 1, next);
				PutInt(nodeId - 1, students[i].id);
				Send(nodeId - 1);
			}
		}
		else
		{
			students[i - 1].id = next;
			students[i - 1].pos = i - 1;
		}
		last = students[i].id;
	}
	
	std::sort(students, students + n, sortStudents);
}

void handleReadStudents(int sender)
{
	int current = GetInt(sender);
	int last = GetInt(sender);
	if (nodeId < numNodes / 2)
	{
		readStudents(current, last);
	}
	else
	{
		readStudentsBackward(current, last);
	}
	
	processOwnQuery();
}

int totalRecieved = 0;
int queries[201];

bool handleAnswer(int sender)
{
	int query = GetInt(sender);
	int total = GetInt(sender);
	
	if (total > numOfStudents / 2)
		total = numOfStudents - total;
	queries[query] = total;
	totalRecieved++;
	
	if (totalRecieved == NumberOfQueries())
	{
		for (int i = 1; i <= NumberOfQueries(); i++)
			printf("%d\n", queries[i]);
		return true;
	}
	return false;
}

int main()
{
	nodeId = MyNodeId();
	numNodes = NumberOfNodes();
	masterId = 0;
	
	numOfStudents = NumberOfStudents();
	n = numOfStudents / numNodes;
	int mod = numOfStudents % numNodes;
	if (nodeId < mod)
		n++;
	
	students = new Student[n];
	if (nodeId == masterId)
	{
		int last = SecondNeighbor(1);
		
		PutChar(numNodes - 1, 0);
		PutInt(numNodes - 1, last);
		PutInt(numNodes - 1, 1);
		Send(numNodes - 1);
		
		readStudents(1, last);
		processOwnQuery();
	}
	
	bool running = true;
	while (running)
	{
		/* COMMANDS:
			0 - read students - int:current, int:last
			1 - query to - int:query, int:sum
			2 - query from - int:query, int:sum
			3 - move query - int:query
			4 - answer - int:query, int:sum
			5 - exit
		*/
		int sender = Receive(-1);
		char msg = GetChar(sender);
		if (msg == 0)
		{
			handleReadStudents(sender);
		}
		else if (msg == 1 || msg == 2)
		{
			handleQuery(sender, msg);
		}
		else if (msg == 3)
		{
			int query = GetInt(sender);
			processQuery(query);
		}
		else if (msg == 4)
		{
			if (handleAnswer(sender) == true)
			{
				running = false;
				for (int i = 0; i < numNodes; i++)
				{
					if (i == nodeId)
						continue;
					
					PutChar(i, 5);
					Send(i);
				}
			}
		}
		else if (msg == 5)
		{
			running = false;
		}
		
	}
	
	delete[] students;
	return 0;
}