Problem A
Färga håret

Din kompis har ledsnat på sin naturliga hårfärg och har bestämt sig för att det är dags för förändring. Varje dag har din lokala hårsalong stor rea på en av sina $10$ hårfärger (ingen av dem är din kompis naturliga hårfärg). De håller ett preliminärt schema över deras reor de kommande $N$ dagarna men varnar om att schemat kan ändras i framtiden. Att färga håret är såklart inte något som kan göras halvhjärtat, så din kompis tänker göra upp en plan för hur han ska färga håret den närmaste tiden.

En sådan plan bestämmer vilka dagar din kompis ska gå och färga håret. När han färgar håret väljer han alltid färgen som är på rea eftersom det blir för dyrt annars. Sammanlagt finns det $2^N$ möjliga planer. Han godtar dock inte alla planer: han vill såklart inte färga håret samma färg två gånger i rad.

Du har blivit ombedd av kompisen att räkna ut hur många olika sådana planer han skulle kunna skapa. Varje gång du kommer med ett svar säger din kompis dock att hårsalongen har uppdaterat sitt schema och bytt vilken färg som är på rea en av dagarna.

Eftersom svaret kan bli väldigt stort ska du skriva ut det modulo $2^{64}$. Detta är samma som resten av svaret efter att det har delats med $2^{64}$. I de flesta programmeringsspråk beräknas allting modulo $2^{64}$ automatiskt om du använder osignerade 64-bitars heltal. I C++ kan du använda unsigned long long.

Indata

Den första raden i indatan innehåller två heltal, $N$ och $Q$ ($1 \leq N \leq 10^5$, $0 \leq Q \leq 10^5$), antalet dagar i schemat och antalet schemauppdateringar.

Därefter följer $N$ heltal $a_i$ ($0 \leq a_i \leq 9$), där $a_i$ betyder att det är rea på färg $a_i$ under dag $i$.

Därefter följer $Q$ rader som vardera innehåller heltalen $i$ och $v$ ($1 \leq i \leq N$, $0 \leq v \leq 9$), vilket betyder att dag $i$ nu har rea på färg $v$.

Notera att både $a_i$ och $v$ är väldigt små.

Utdata

Skriv först ut antalet färgningsplaner som kan skapas från det ursprungliga schemat modulo $2^{64}$.

Skriv därefter ut antalet planer som kan skapas modulo $2^{64}$ efter varje uppdatering.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

Det finns 4 planer: antingen kan kompisen låta bli att färga håret helt, eller färga håret exakt en gång.

Förklaring av exempelfall 2

De 7 planerna är:

• $[]$

• $[0]$

• $[1]$

• $[0 1]$

• $[0]$

• $[1 0]$

• $[0 1 0]$

Notera alltså att planerna som endast innehåller färgen $0$ räknas två gånger, eftersom det är olika planer om man färgar håret på olika dagar även om det är samma färg.

3 0
0 0 0

4

3 0
0 1 0

7

4 2
0 1 2 0
1 1
4 1

15
12
10