Remote Training on Programming

Как известно, задачей оптимизации называется задача о нахождении экстремума (минимума или максимума) заданной функции в некоторой области. Как правило, рассматриваются области, принадлежащие и заданные набором равенств и неравенств.

Постановка задачи состоит из следующих частей:

1.     Задание допустимого множества: .

2.     Задание целевой функции:

3.     Задание критерия поиска: минимум или максимум.

В нашей задаче будем считать, что

,

а функция имеет вид

.

Проще говоря, у нас есть n диапазонов чисел от A_i до B_i. Из каждого диапазона  нужно взять по одному целому числу x_i, так чтобы сумма разностей между соседями была максимальна (либо минимальна в зависимости от условия).

Нам известна первая пара целых чисел A₁ и B₁. Каждая следующая вычисляется по формуле

A_i = (2*A_i-1 + 3*B_i-1) mod 1111111

B_i = (4*A_i-1 - 2*B_i-1 ) mod 1111111

Если в результате вычислений получается A_i > B_i, то его следует понимать как интервал чисел от B_i до A_i , не меняя сами числа местами.

Формат входного файла

В первой строке входного файла содержится  целое число n (2 ≤ n ≤ 10⁹) — размерность пространства X.

В следующей строке приведены целые числа, разделенные пробелом  А₁ и B₁. (-10⁹ ≤ A₁ ≤ B₁≤ 10⁹).

В последней строке приведен критерий: min — в случае минимизации результата, max — в случае максимизации. Все числа целые.

Формат выходного файла

В единственной строке выведите целое число — требуемый экстремум.

Пример