Xorshift+ ennustamine

문제

Vaatleme pseudojuhuslike arvude generaatorit:

  function xorshift()
    last_value = internal_value
    for i = 1 to M do
      if S[i] < 0 then
        internal_value = internal_value ^ (internal_value >> -S[i])
      else
        internal_value = internal_value ^ (internal_value << S[i])
    return last_value + internal_value

kus

• last_value on $NN$-bitine lokaalne muutuja;
• internal_value on $NN$-bitine globaalne muutuja, mille algväärtus ei ole teada;
• S on globaalne $MM$-elemendiline konstantide massiiv, mille väärtused on teada;
• ^ tähistab bitikaupa välistava või tehet (XOR); selle tehte tulemuses on $00$ need bitid, kus operandide vastavad bitid on võrdsed, ja $11$ need, kus operandide vastavad bitid on erinevad; näiteks $1012=610\; \backslash mathbin\{^\}\; 12\; =\; 6$, sest arvu $1010$ kahendkuju on 1010 ja arvu $1212$ kahendkuju 1100; seega peab tehte tulemus olema 0110, mis on arvu $66$ kahendkuju;
• << ja >> tähistavad bitikaupa vasakule ja paremale nihutamise tehteid; $NN$-bitise arvu $ss$ biti võrra vasakule nihutamisel kustutatakse arvu kahendkujust $ss$ vasakpoolsemat bitti ja lisatakse paremale $ss$ bitti väärtusega $00$; näiteks $44$-bitise muutuja korral , sest $66$ kahendkuju on 0110, millest $22$ vasaku biti kustutamisel saame 10 ja sellele paremale kahe $00$-biti lisamisel 1000, mis on arvu $88$ kahendkuju; paremale nihutamisel kustutatakse bitte paremalt ja lisatakse vasakule;
• + tähistab liitmist, kus tulemusest kasutatakse ainult $NN$ parempoolsemat bitti;
• internal_value algväärtus ei ole $00$ ja S elementide väärtused on sellised, et funktsiooni xorshift lõpmatult välja kutsudes omandab internal_value kõik väärtused $1\dots 2^N-11\; \backslash ldots\; 2^N-1$.

Kirjutada program, mis saab $KK$ järjestikust funktsiooni xorshift tagastatud väärtust ja leiab nende põhjal järgmisena tagastatava väärtuse.

입력

Tekstifaili esimesel real on kolm täisarvu $NN$ ($2\le N\le 642\; \backslash le\; N\; \backslash le\; 64$), $MM$ ($2\le M\le 102\; \backslash le\; M\; \backslash le\; 10$) ja $KK$ ($100\le K\le 200000100\; \backslash le\; K\; \backslash le\; 200\backslash ,000$). Faili teisel real on $MM$ täisarvu $S_{i}S\_i$ ($1-N\le S_i\le N-11-N\; \backslash le\; S\_i\; \backslash le\; N-1$). Faili kolmandal real on $KK$ täisarvu $V_{j}V\_j$ (), funktsiooni xorshift väärtused $KK$ järjestikusel väljakutsel.

출력

Tekstifaili ainsale reale väljastada üks täisarv, funktsiooni xorshift järgmisel väljakutsel tagastatav väärtus.

2 2 100
-1 1
0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0 1 3 0

1