Рассмотрим последовательность чисел x0, x1, ..., xn-1, сгенерированных при помощи следующей формулы:

x0 = p,

xi = (a * xi-1 * xi-1 + b * xi-1 + c) mod m, где 0 < i < n

Создайте из этих чисел Связный Список: List = x0 → x1 → ... → xn-1.

Пусть k = xn mod n. Если xn < m / 2, то tail → next пусть указывает на k-ый элемент. Иначе tail → next = NULL. Установите согласно этому условию значение указателя tail → next.

Рассмотрим пример: p = 1, a = 1, b = 1, c = 1, m = 100, n = 5. Здесь List = 1 → 3 → 13 → 83 → 73, xn = 3, поэтому k = 3 < 100 / 2 = m / 2 и tail → next указывает на третий элемент, равный 83 (позиции элементов в Списке начинаются с 0).

Реализуйте метод hasCycle, который определит имеется ли в Списке цикл.

Напишите код согласно следующего интерфейса:

class Node

{

public:

int data;

Node *next;

Node() : next(NULL) {};

Node(int data, Node *next = NULL) : data(data), next(next) {};

};

class List

{

public:

Node *head, *tail;

List() : head(NULL), tail(NULL) {};

void addToTail(int val); // Добавьте число val в конец Связного Списка

int hasCycle(void) // Вернуть 1 если список имеет цикл, иначе вернуть 0

};

Вы можете создавать (использовать) по необходимости дополнительные методы.

Входные данные

В одной строке заданы шесть чисел: p, a, b, c, m, n. Все числа целые в промежутке от 0 до 1000, m и n больше 0.

Выходные данные

Выведите 1, если Связный Список имеет цикл, и 0 иначе.