Min and Max#5515
Two kittens, Min and Max, have written a sequence of integers on a sheet of paper and are playing the following game. On each turn, a kitten can choose two adjacent numbers and replace them with either their minimum or maximum. The kittens alternate turns. The game continues until only one number remains on the sheet. Kitten Min wants to make this final number as small as possible, while kitten Max wants it to be as large as possible.
Assuming both kittens are infinitely intelligent and play optimally, determine which number will remain on the sheet at the end of the game.
The first line contains one integer — the number of numbers written by the kittens (1 \leq n \leq 5 \cdot 10^7).
The second line contains the name of the kitten who goes first: Min if kitten Min plays first, or Max if kitten Max plays first.
Since the sequence can be very long, you are given numbers 0 \leq c_1, a, b < 2^{32}, and each element of the sequence is generated from the previous one by the formula
Print the only number that will remain on the sheet after the entire game.
Example 1