1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 10 * 1000 * 1000 + 17;
bool s[MAXN];
int a[MAXN];
map<int, int> ile[1000 * 1000];
vector<int> pier;
int akt[MAXN];
set<int> sss;

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;

    for (ll i = 2; i <= (n/2 + 3); i ++) {
        if (!s[i]) {
            for (ll j = i * i; j <= ll(n/2 + 3); j += ll(i)) {
                s[j] = 1;
            }
            pier.pb(i);
        }
    }

    akt[0] = MAXN * 10;

    int m = int(pier.size());

    int x;
    int wyn = 0;

    if (n != 1) {
        while (q --) {
            cin >> x;

            if (!a[x]) {
                sss.insert(x);
                for (int i = 0; i < m; i ++) {
                    akt[ile[i][x % pier[i]]] --;
                    ile[i][x % pier[i]] ++;
                    akt[ile[i][x % pier[i]]] ++;
                    wyn = max(wyn, ile[i][x % pier[i]]);
                }
            } else {
                sss.erase(x);
                for (int i = 0; i < m; i ++) {
                    akt[ile[i][x % pier[i]]] --;
                    ile[i][x % pier[i]] --;
                    akt[ile[i][x % pier[i]]] ++;
                    if (akt[wyn] == 0) {
                        wyn --;
                    }
                }
            }
            a[x] ^= 1;

            int w = 0;

            if (int(sss.size()) > 2) {
                w = 2;
            }
            if (int(sss.size()) == 2) {
                int i = *sss.begin();
                if (a[i - 1] == 1 || a[i + 1] == 1) {
                    w = 1;
                } else {
                    w = 2;
                }
            }
            if (int(sss.size()) == 1) {
                w = 1;
            }

            cout << max(w, wyn) << "\n";
        }
    } else {
        while (q --) {
            cin >> x;

            a[x] ^= 1;

            cout << a[x] << "\n";
        }
    }

    return 0;
}