#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define ll long long
using namespace std;

typedef struct {
    int val;
    int arr;
    int index;
} nzm;

/*ll xoruj(nzm el, vector<nzm> d[]) {
    if (el.arr == 0) return el.val;
    else {
        ll tempxor = 0;
        for (auto rec : d[el.index]) {
            tempxor = tempxor ^ xoruj(rec, d);
        }
        return tempxor;
    }
}*/

// opt: izbaci 1

int main()
{
    ll n; int k;
    scanf("%lld %d", &n, &k);
    int deli[k];
    for (int i=0; i<k; i++) scanf("%d", &deli[i]);

    sort(deli, deli+k);
    vector<nzm> d[k];
    nzm tmp;
    for (int i=1; i<k; i++) { // skip 1
        // tr: del[i]
        //printf("provera za deli[%d]=%d\n", i, deli[i]);
        int j=i-1;
        bool skip=false;
        tmp.val = deli[i]; tmp.arr = 0; tmp.index = i;
        d[i].push_back(tmp);
        while (j>0) {
            if (deli[i]%deli[j]==0) {
                //printf("%d deli %d\n", deli[i], deli[j]);
                tmp.val = deli[j]; tmp.arr = 0; tmp.index = j;
                //printf("d[%d][1].val=%d\n", j, d[j][1].val);
                if (d[j][1].val != 1) tmp.arr = 1;
                d[i].push_back(tmp);
                if (tmp.arr == 1) break;
                //skip = true;
                //break; // MOZDA BREAK AKO ARR = 1
            }
            j--;
        }

        if (!skip) {
            tmp.val = 1; tmp.arr = 0; tmp.index = 1;
            d[i].push_back(tmp);
        }
    }

    /*ll xora[k];
    for (int i=0; i<k; i++) {
        // trenutni je d[i] su delioci broja del[i]
        xora[i] = 0;
        for (auto el : d[i]) {
            xora[i] = xora[i] ^ xoruj(el, d);
        }
        cout << xora[i] << endl;
    }*/

    

    map<int, ll> xorm;
    xorm[1] = 1;
    for (int i=1; i<k; i++) {
        xorm[deli[i]] = 0;
        for (nzm el : d[i]) {
                if (el.val==1) continue;
            if (el.arr == 0) {
                    xorm[deli[i]] = xorm[deli[i]] ^ el.val;
                //printf("x(%d) ^= %d = %d\n", deli[i], el.val, xorm[deli[i]]);
            }
            else {
                    xorm[deli[i]] = xorm[deli[i]] ^ xorm[el.val];
                    //printf("x(%d) ^= %d *\n", deli[i], xorm[el.val]);
            }
        }
        //printf("xor(%d)= %lld\n", deli[i], xorm[deli[i]]^1);
    }
    return 0;

}