Final exams P87812

Professor Oak is dealing with the final exams of his course. He can either:

• Put an exam on top of the other exams on his desk.

• Remove the exam on top.

• Check which is the best qualification among the exams on his desk.

Please help him to do it efficiently.

Input

To avoid large input files, the commands and numbers will be pseudo-randomly generated. The integer sequence will be produced by the following linear congruential generator:

A := 8433437992146984169
B := 7905438737954111703
X := S   // initial seed
function nextinteger():
    X := (A*X + B) mod 2^64
    return X / 2^32

For each number $y$ returned, the command will be:

• “Put”, if $y \not \equiv 0 \bmod 4$. The grade of the exam will be the next pseudo-random number generated, which should not be counted as a command.

• “Remove”, if $y \equiv 0 \bmod 4$ and $y \not \equiv 0 \bmod 8$.

• “Check”, if $y \equiv 0 \bmod 4$ and $y \equiv 0 \bmod 8$.

Input consists of several cases, each with the number of instructions (between 0 and $10^6$) and the initial seed $S$ (between 0 and $2^{64}-1$). Print “EMPTY DESK” every time that Prof. Oak tries to remove an exam or check the best qualification but there are no exams on his desk.

Output

For every case, print the best qualification for every query, together with the error messages. Print a blank line after every case.