Мин и Макс
Два котёнка - Мин и Макс - записали на листе бумаги последовательность целых чисел и играют в следующую игру. Каждым ходом котёнок может взять два соседних числа и оставить из них либо минимальное, либо максимальное. Ходы делаются по очереди. Игра продолжается до тех пор, пока не останется ровно одно число. Котёнок Мин хочет добиться, чтобы это число было минимально возможным, котёнок Макс - чтобы это число было максимально возможным.
Считая, что оба котёнка бесконечно умны и действуют оптимально, выведите, какое число останется на листе бумаги.
Входные данные
В первой строке ввода находится одно целое число n - количество чисел, записанных котятами (1 ≤ n ≤ 5·10^7). Во второй строке находится имя котёнка, который ходит первым: "Min", если первым ходит котёнок Мин, и "Max", если первым ходит котёнок Макс. Так как последовательность может быть очень длинной, вам даны числа 0 ≤ c_1, a, b <2^32, а каждый элемент последовательности получается из предыдущего по формуле
c_i = c_{i-1}·a + b) mod 2^32.
Выходные данные
Выведите единственное число - то, которое останется на листе бумаги в конце игры.