Ősi Programozó járja a falvakat amelyeket internethiány súlyt, és kriptovalutát oszt. Miért? Senki sem tudja. Útja folyamán áthaladt k falun, minden \(i\)-edik faluban \(a_i\) programozó lakik, akik internet hiányában élvezik a napot, fákat és a többi csodálatos dolgot amely körül veszi őket. Ősi Programozó kilogramm kriptovalutát vitt magával, amelyet a Nagyszámok törvénye alapján oszt szét: amelyik falunak nagyobb a sorszáma, több kriptovalutát kap.

Konkrétan: az első falu minden programozója annyi kilogramm kriptovalutát kapott, amennyi az \(n\) szám szájegyeinek összege; a második falu minden programozója annyi kilogramm kriptovalutát kapott amennyi az \(n\) szám számjegyei négyzetének összege; stb.; a \(k\)-adik falu minden programozója annyi kilogramm kriptovalutát kapott amennyi az \(n\) szám számjegyei \(k\)-adik hatványának összege. Miután Ősi Programozó bejárta az összes falvat, rájött, hogy az összes kriptovalutát, amit magával hozott, éppen szétosztotta, a boldogságtól két örömkönnyet hullatott.

Meghatározni, hány kilogramm kriptovalutát vitt magával Ősi Programozó, ha tudjuk, hogy ez a szám \(x\) és \(y\) között található (az intervallumba \(x\) és y is beletartozik ). Azt is tudjuk, hogy Ősi Programozó kedvenc kriptovalutája nem a kriptonit.

Bemenet

A szabványos bement első sorában három szám \(x\), \(y\) és \(k\) található, ebben a sorrendben. Ezek az \(n\) szám határait jelentik, és a falvak számát. A következő sorban \(k\) természetes szám áll. Ezek az \(a_i\) értékek, amelyek sorban a programozók számát jelentik egy-egy faluban.

Kimenet

A szabványos kimenet első és egyetlen sorában az \(n\) szám áll, a kriptovaluta kilogrammjainak száma, amelyet Ősi Programozó magával vitt. Ha az adott intervallumban nincs megoldás, kiíratni-1; ha viszont az adott intervallumban több megoldás is van, kiíratni bármelyiket.

Korlátozások

• \(1 \leq x \leq y \leq 10^{18}\)
• \(1 \leq k \leq 10^5\)
• \(1 \leq a_i \leq 10^{18}\) minden \(i \in \{1,2,...,k\}\)

A tesztpéldák 5 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: \(|x-y| \leq 10^3\).
• Tesztpéldák, melyek \(10\) pontot érnek: \(|x-y| \leq 10^7\).
• Tesztpéldák, melyek \(20\) pontot érnek: \(k \leq 2\).
• Tesztpéldák, melyek \(20\) pontot érnek: \(k = 2021\).
• Tesztpéldák, melyek \(40\) pontot érnek: Nincs külön korlátozás.

Példák

1. példa

Bemenet

18000 25000 3
30 65 21

Kimenet

20528

Magyarázat

Ha Ősi Programozó \(20528\) kilogramm kriptovalutát vitt magával, az 1. falu programozóinak fejenként \(2+0+5+2+8=17\) kilogrammot, a 2. falu programozóinak fejenként \(2^2+0^2+5^2+2^2+8^2=97\) kilogrammot, a 3. falu programozóinak fejenként \(2^3+0^3+5^3+2^3+8^3=653\) kilogrammot osztott szét. Összesen tehát \(30\cdot17+65\cdot97+21\cdot653=20528\) kilogramm kriptovalutát osztott szét, vagyis az összeset szétosztotta, ami a célja is volt. Fontos észre venni, hogy bár a \(29630\) is kielégíti az előző feltételeket, nem jó eredmény, mert nem tartozik bele az \([18000, 25000]\) intervallumba..

2 példa

Bemenet

45 60 1
7

Kiment

-1

Magyarázat

Annak ellenére, hogy több szám is megfelel a szétosztás feltételeinek, (pl. \(21\)) egyik sem tartozik bele az adott \([45,60]\) intervallumba, ezért -1-et kell kiíratni.