# Interactive Casino

This is interactive problem.

In the Interactive Casino game "Binary Roulette" is very popular. Here are the rules of the game.

Initially the player has 160 tokens. In one turn player can bet any positive integer amount of tokens, as long as it does not exceed number of tokens player currently has. Inside of slot machine an integer $x$between $0$and $2^{20} -1$is generated. If sum of bits of this integer is odd, then player wins (i.e. returns his bet and additional k tokens), otherwise the player loses his bet. Note that player does not know value of $x$. If the player has zero tokens, game is lost. If the player makes more than 200 bets, game is lost. If the player at some time has 200 tokens, he won the game. You found on the Algoleaks site that each next integer on the sloth machine is generated using the formula $x _i = (487237*x _{i-1} + 1011807)mod 2^{20}$. Source of $x _1$, unluckly, on this site is not revealed.

Your goal is to ensure the victory.

# Input

Your program will receive on the input one integer — number of tokens You currently have or  - 1 in case when game is over by some reason.

# Output

If you received $-1$, immediately exit your program with code 0 (otherwise you may get the random verdict from the system). Otherwise, if you received integer T > 0, print one integer between 1 and T, inclusively — your next bet. Dont forget to print end-of-line character and flush the output.

# Example

input

160
155
165
180
-1

output

5
10
15
20

# Solution

# 思路

注意到这个哈希序列的循环长度最大为$2^{20}$，可以预处理出代表输赢情况的01序列。 通过金钱的变化判断输赢，与预处理的01序列作匹配。 当尝试的局数不多的时候可能会有多个匹配，玩上一段时间之后一定能剩下唯一的一段完全匹配的序列，之后用这段序列预测老虎机下一个结果如何即可。

# Code

#include <cstdio>
#include <queue>
#include <assert.h>
#define LL long long
using namespace std;
const int N = 2e6;
int g[N]; bool win[N];

int top = 1 << 20;
void init()
{
    for (LL x = 0; x < top; ++x)  
    {  
        g[x] = (x * 487237 + 1011807) % top;
        int y = x;  
        int sum = 0;  
        while (y)
        {
            sum += y & 1;
            y >>= 1;
        }  
        win[x] = sum & 1;
    }  
}

queue<int> q[2];
void solve()
{
    int now, tag = 0, money;
    for (int i = 0; i < top; ++i)
        q[tag].push(i);
    scanf("%d", &now);
    while (true)
    {
        printf("1\n");
        fflush(stdout);
        scanf("%d", &money);
        bool wins = (money == now + 1);
        while (!q[tag].empty())
        {
            if (win[q[tag].front()] == wins)
                q[tag ^ 1].push(g[q[tag].front()]);
            q[tag].pop();
        }
        
        now = money; 
        tag ^= 1;
        if (q[tag].size() == 1 && win[q[tag].front()])
        {
            printf("%d\n", 200 - now);
            fflush(stdout);
            return;
        }
    }
}
int main()
{
    init();
    solve();
    return 0;
}