#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;
class Darray {
    public:
        Darray() {
            capacity = 100;
            size = 0;
            data = new int[capacity];
        };
        ~Darray();
        int& operator[](int);
        void pushback(int x);
        void clear(void);
        int length(void);
        int cap(void);
    private:
        void resize(void); // double the capacity
        int *data;
        int capacity;
        int size;
};
class randGen {
private:
    unsigned int z1, z2, z3, z4;
public:
    randGen(int seed) {
        z1 = seed;
        z2 = seed << 10;
        z3 = seed << 20;
        z4 = seed << 30;
    };
    unsigned int next() {
        unsigned int b;
        b  = ((z1 << 6) ^ z1) >> 13;
        z1 = ((z1 & 4294967294U) << 18) ^ b;
        b  = ((z2 << 2) ^ z2) >> 27; 
        z2 = ((z2 & 4294967288U) << 2) ^ b;
        b  = ((z3 << 13) ^ z3) >> 21;
        z3 = ((z3 & 4294967280U) << 7) ^ b;
        b  = ((z4 << 3) ^ z4) >> 12;
        z4 = ((z4 & 4294967168U) << 13) ^ b;
        return (z1 ^ z2 ^ z3 ^ z4);
    }
};
const int mul = 9487;
const int mod = 99999989;
typedef long long ll;
class rollingHash {
    public:
    rollingHash() {
        hash = 0;
    }
    void push(int x) {
        hash = ((hash * mul) % mod + x) % mod;
    }
    ll getHash() {
        return hash;
    }
    private:
        ll hash;
};
//#include "function.h"
Darray::~Darray(){
    delete[] data;
}
int& Darray::operator[](int x){
    return data[x];
}
void Darray::pushback(int x){
    if(size==capacity){
        resize();
    }
    //cout<<"x="<<x<<endl;
    data[size]=x;
    size++;
}
void Darray::clear(void){
    size=0;
}
int Darray::cap(void){
    return capacity;
}
int Darray::length(void){
    return size;
}
void Darray::resize(void){
    capacity*=2;
    int* newdata=new int[capacity];
    for(int i=0;i<capacity/2;i++){
        newdata[i]=data[i];
    }
    delete[] data;
    data=newdata;
}
void test(){
    Darray arr;
    for (int i = 0; i < 5; i++) arr.pushback(i*i);
    arr[2] += 100 + arr[3];
    for (int i = 0; i < arr.length(); i++)
        cout << arr[i] << ' ';             // Print: 0 1 113 9 16
    
    cout <<"capaciy="<< arr.cap() << endl;   // Print: 5
    arr.pushback(6);
    
    for (int i = 0; i < arr.length(); i++)
        cout << arr[i] << ' ';
    cout<<endl;
    
    arr.clear();
    cout << arr.length() << endl;          // Print: 0
    cout<<arr.cap()<<endl;
    arr.pushback(9487);
    cout << arr.length() << ' ' <<arr.cap()<<' '<< arr[0] << endl;  // Print: 1 9487
}
int main() {
    
    int seed;
    //cin >> seed;
    seed=9487;
    randGen rand(seed);
    rollingHash hash;
    // check single array
    {
        Darray arr;
        int t = 1000000;
        int check_len = rand.next() % t;
        for (int i = 0; i < t; i++) {
            int tmp = rand.next();
            arr.pushback(tmp);
            if (check_len == i) {
                int len = arr.length();
                hash.push(len);
            }
        }
        
        for (int i = 0; i < t / 2; i++) {
            int tmp = rand.next();
            int ind = rand.next() % arr.length();
            arr[ind] = tmp;
        }
        
        for (int i = 0; i < t; i++) {
            int ind = rand.next() % t;
            int out = arr[ind];
            hash.push(out);
            hash.push(ind);
        }
        
        arr.clear();
        int t2 = rand.next() % (t / 3);
        for (int i = 0; i < t2; i++) {
            int tmp = rand.next();
            
            arr.pushback(tmp);
            
        }
        
        for (int i = 0; i < t2 / 2; i++) {
            int ind = rand.next() % t2;
            int out = arr[ind];
            hash.push(out);
            hash.push(ind);
        }
        
    }
    // test multiple arr
    for (int x = 0; x < 4; x++) {
        Darray arr[100];
        int t = 1000000;
        int check_len = rand.next() % t;
        for (int i = 0; i < t; i++) {
            int ind = rand.next() % 100;
            int tmp = rand.next();
            arr[ind].pushback(tmp);
        }
        for (int i = 0; i < 100; i++) {
            hash.push(arr[i].length());
        }
        for (int i = 0; i < t / 10; i++) {
            int ind = rand.next() % 100;
            int ind2 = rand.next() % arr[ind].length();
            int tmp = rand.next();
            arr[ind][ind2] = tmp;
        }
        for (int i = 0; i < t; i++) {
            int ind = rand.next() % 100;
            int ind2 = rand.next() % arr[ind].length();
            hash.push(arr[ind][ind2]);
            hash.push(ind);
            hash.push(ind2);
        }
        for (int i = 0; i < 50; i++) {
            int ind = rand.next() % 100;
            arr[ind].clear();
            hash.push(arr[ind].length());
            hash.push(ind);
        }
        int t2 = t / 3;
        for (int i = 0; i < t2; i++) {
            int ind = rand.next() % 100;
            int tmp = rand.next();
            arr[ind].pushback(tmp);
        }
        for (int i = 0; i < 100; i++) {
            hash.push(arr[i].length());
            hash.push(arr[i].length());
        }
        for (int i = 0; i < t; i++) {
            int ind = rand.next() % 100;
            int ind2 = rand.next() % arr[ind].length();
            hash.push(arr[ind][ind2]);
            hash.push(ind);
            hash.push(ind2);
        }
        cout<<"multiple AC\n";
    }
    cout << hash.getHash() << " AC\n";
    return 0;
}