Древни Програмер иде од села до села погођених несташицом интернета и дели криптовалуте. Зашто? Нико не зна. На његовом путу нашло се \(k\) села, у \(i\)-том селу је \(a_i\) програмера који се, у недостатку интернета, диве сунцу, дрвећу и другим чудесима која их окружују. Древни Програмер је понео \(n\) килограма криптовалута и дели их према Закону великих бројева - село са већим редним бројем добија већи број криптовалута.

Формалније, сваки програмер првог села добио је онолико килограма криптовалута колики је збир цифара броја \(n\); сваки програмер другог села добио је онолико килограма криптовалута колики је збир квадрата цифара броја \(n\); итд.; сваки програмер \(k\)-тог села добио је онолико килограма криптовалута колики је збир \(k\)-тих степена цифара броја \(n\). Након што је Древни Програмер обишао сва села и одјахао у сутон, схватио је да је поделио тачно све криптовалуте које је понео; и би му драго и пусти уздах и две сузе радоснице.

Одредити колико је килограма криптовалута понео Древни Програмер уколико је познато да је тај број између \(x\) и \(y\) (укључиво), као и да омиљена криптовалута Древног Програмера није криптонит.

Опис улаза

У првом реду стандардног улаза налазе се три природна броја \(x\), \(y\) и \(k\) који, редом, представљају границе за број \(n\) и број села. У наредном реду налази се \(k\) природних бројева \(a_i\) - број програмера по селима, редом.

Опис излаза

У првом и једином реду стандардног излаза исписати један природан број \(n\) - број килограма криптовалута које је Древни Програмер понео са собом. Уколико нема решења у задатом интервалу, исписати -1; уколико има више решења (у задатом интервалу) исписати било које.

Ограничења

• \(1 \leq x \leq y \leq 10^{18}\)
• \(1 \leq k \leq 10^5\)
• \(1 \leq a_i \leq 10^{18}\) за свако \(i \in \{1,2,...,k\}\)

Тест примери су подељени у \(5\) дисјунктних група:

• У тест примерима вредним \(10\) поена: \(|x-y| \leq 10^3\).
• У тест примерима вредним \(10\) поена: \(|x-y| \leq 10^7\).
• У тест примерима вредним \(20\) поена: \(k \leq 2\).
• У тест примерима вредним \(20\) поена: \(k = 2021\).
• У тест примерима вредним \(40\) поена: Без додатних ограничења.

Примери

Пример 1

Улаз

18000 25000 3
30 65 21

Излаз

20528

Објашњење

Уколико је Древни Програмер понео \(20528\) килограма криптовалута, тада сваки програмер из 1. села добија по \(2+0+5+2+8=17\) килограма, сваки програмер из 2. села добија по \(2^2+0^2+5^2+2^2+8^2=97\) килограма и сваки програмер из 3. села добија по \(2^3+0^3+5^3+2^3+8^3=653\) килограма. Дакле, укупно је подељено \(30\cdot17+65\cdot97+21\cdot653=20528\) килограма, тј. подељене су све криптовалуте као што се и захтевало. Обратити пажњу да иако и број \(29630\) задовољава претходне услове, он не припада опсегу \([18000, 25000]\) па није решење.

Пример 2

Улаз

45 60 1
7

Излаз

-1

Објашњење

Иако постоји неколико бројева који испуњавају услове о подели (нпр. \(21\)) ниједан од њих не припада сегменту \([45,60]\) па треба исписати -1.