Background

“Only by finding derivatives of derivatives can you become the best.” As a stubborn tough guy, GodFly is no longer satisfied with simple differentiation.

Problem Description

To prove how stubborn he is, GodFly decided to take on a challenge: compute the $k$-th derivative of an $n$-th degree polynomial function with big integer coefficients. Now he hopes that smart you can… sit there quietly and watch him differentiate. After all, he is a man who can rival Shenwei - TaihuLight.

As GodFly’s friend, xhx hopes you can help him write a program to compute the derivative function and derivative values together with GodFly. If your program can beat his manual calculation, xhx will knock on GodFly’s iron head.

*Some rules for derivatives:

If $f(x)=ax^n$, then $f'(x)=anx^{n-1}$.

If $F(x)=f(x)+g(x)$, then $F'(x)=f'(x)+g'(x)$.

Here, $f'(x)$, $g'(x)$, and $F'(x)$ denote the derivative functions of $f(x)$, $g(x)$, and $F(x)$, respectively.

Do not be scared by derivatives. This problem is not testing that.

Let $g(x)=ax^3+bx^2+c$, then $g(x_0)=ax_0^3+bx_0^2+c$.

The $k$-th derivative means differentiating $k$ times.

New samples: https://pan.baidu.com/s/1w64WmnnGtKyAluxrX3PkNg; testdata has been updated.

Input Format

The first line contains two integers $n,k$, with meanings as described in the statement.

The next line contains a string representing the function, in the form $f(x)=a_{n}x^n+a_{n-1}x^{n-1}+....+a_0x^0$. For any $i$, the term $a_ix^i$ may be absent, or may appear multiple times. All $a_i$ are positive integers, but if a term has coefficient $1$, then $a_i$ is not given; only $x^i$ is written.

The next line contains a number $m$, the number of queries.

The next $m$ lines each contain a number $x_0$, meaning: compute the value of the $k$-th derivative of $f(x)$ at $x_0$. In other words, suppose $g(x)$ is the $k$-th derivative function of $f(x)$, find $g(x_0)$.

There are no extra spaces or blank lines.

Output Format

Output $m$ lines, each containing one number, the required derivative value.

3 2
f(x)=x^3+2x^2+x^1+x^0
2
0
1

4
10

100 80
f(x)=70109x^84+31190x^15+45313x^77+52808x^10+40146x^89+41024x^14+89576x^33+96906x^24+5709x^55+92657x^6+60729x^97+87451x^57+88440x^85+25928x^66+48048x^71+92676x^7+15167x^18+63997x^66+58477x^36+34120x^65+27725x^29+31391x^23+30665x^50+84699x^16+64456x^6+26791x^68+66327x^26+36721x^96+72893x^100+22073x^24+38681x^64+9925x^63+92854x^22+27301x^23+39910x^79+24609x^81+47423x^93+6710x^90+96661x^70+22479x^72+17422x^57+78832x^3+1010x^72+7876x^40+3790x^70+84553x^69+60952x^52+58198x^81+48082x^39+45635x^23+71833x^54+11456x^14+31619x^18+94591x^53+32180x^14+61596x^96+11236x^62+39754x^45+789x^39+96093x^91+13491x^17+38611x^18+7604x^34+23457x^9+84129x^48+50188x^59+59588x^87+99259x^52+94768x^57+17553x^65+38948x^66+34133x^76+61695x^54+41424x^14+23408x^23+1575x^65+98294x^21+82817x^4+41010x^11+75176x^88+82645x^70+81244x^48+12859x^71+71380x^8+90927x^10+73190x^23+55452x^34+67654x^57+48173x^22+22848x^53+22784x^16+96989x^75+74537x^9+80471x^13+63024x^85+38481x^62+20400x^61+3207x^9+89666x^11+99966x^44+49383x^11+57688x^20+43007x^85+21701x^55+18068x^71+14981x^52+8041x^42+70259x^33+63961x^82+70824x^18+96439x^1+6041x^43+50481x^5+78427x^29+64408x^32+48512x^37+99528x^36+63451x^55+33530x^41+11368x^3+44932x^84+99688x^33+2055x^49+60575x^52+2193x^49+65449x^19+6642x^84+64745x^55+40036x^81+86351x^4+36277x^48+34019x^91+63859x^81+24462x^8+46233x^8+64099x^78+15057x^38+56049x^92+54612x^9+86998x^7+15958x^54+5173x^48+27728x^96+90161x^99+59838x^71+56099x^55+95160x^2+66444x^89+54566x^96+63691x^24+64234x^46+25147x^86+24456x^29+3514x^68+94213x^96+32045x^89+14389x^23+89551x^20+5364x^92+37504x^73+84939x^11+75135x^90+43003x^58+89139x^69+57492x^19+81034x^84+84477x^85+58295x^2+13732x^54+38998x^27+41044x^8+36315x^35+36717x^63+23252x^35+71286x^21+89111x^23+46468x^33+69056x^74+68451x^20+70403x^92+68230x^10+99686x^89+40862x^15+81643x^4+35732x^4+46296x^52+27400x^12+73264x^68+60140x^32+7691x^88+68718x^56+89783x^94+82820x^17+54487x^25+38403x^38+14902x^20+62503x^30+22691x^19+22765x^53+38058x^89+56132x^8
10
68881
11082
81085
62791
24348
17842
4169
35352
5970
62884

16164240066651387562233717301528224969937465373558098015262037027386569033764424458589576758191332209048578992964215681542368338708891051016993923981103415501578871678233991105755103051233486979089239855976079907362208481280000000000000000000
2182415680199447981440641146519198659607077509954309166209248162324864452442827593289098825979096442606243478952222902205343921078278568113665227454286771491416704568924623072727112114731118574714432341934080000000000000000000
422062345638238714739738519709990563603589380455050149059126176370564404652221274586130148555137105128697765829042063701137700058889602612021604742696342353192426896358610967606518173419498516745741373670540528424373033369600000000000000000000
2538134110912799647825063614412363226524317612152769944265617771344449232998633322212149486534945299900387663134035580713149883409969837626763922106020781745065444506920047539106732462229963056457132916655382266009175982080000000000000000000
14991156446236176472502265880432966422015445276733818020404968064741525302926159825161216310702190973624698482701628021749937122966049505110718061754978132745243635634094880836725969058654388943804568845440390266880000000000000000000
29884196573248406556002162301876815395302859901002567421986254945117587639735221615275195608354283425713168881991894459281778355276041429272933416204370972475808889065607037634764929408175999307387754704567009280000000000000000000
7034423875123551962182784353450104496557971298184125552888776318750413078332260250166314564290913379761359968021613709898383403786934866343717269767517868839058663822072847509897027068564795985756160000000000000000000
25992477245017120878983780820866398302559273825548192272216377072453312969834218142751826473940478236447308492208306657193432677046691735517736829469276821419271533107875650191893196069260108040752114150874519416340480000000000000000000
9248461232577723346174268301761164329173345863690159750635506426262976168364385773072687017079604052061927750150164792050863501012462262384745784394685777588084492205111843685947224930396082214744883200000000000000000000
2614386253805989523417576022989825195115049811637606864181649322898595113377432131993964109861291017592215861090255200834838990231767641551915513875471667690003413999293225510105639008531615901769130992569786115253086453760000000000000000000

Hint

Constraints

For $30\%$ of the data: $n\le5$, $a_i\le100$, $x_0\le100$, and for any $0\le i\le n$, the term $a_ix^i$ appears exactly once, and the input is guaranteed to be sorted in decreasing order by $i$.

Another $10\%$ of the data: $k=0$.

Another $10\%$ of the data: $k=1$.

Another $10\%$ of the data: $n=k$.

For $100\%$ of the data: $n\le100$, $k\le n$, $m\le10$, $a_i\le10^5$, $x_0\le10^5$.

Sample Explanation

Differentiate $f(x)$. The first derivative is $f'(x)=3x^2+4x+1$. Differentiate again to get the second derivative: $f''(x)=6x+4$. Therefore, the required values are $f(0)=6*0+4=4$ and $f(1)=6*1+4=10$.

Notes

PS: Worried that everyone will complain about too much code (the setter is lazy), this version has been simplified a lot compared to the original problem.

If you get an early AC, you may want to read a duel between two “iron-head” tough guys:

“Director Feng Differentiates Zheng Babang to Death with Three Derivatives”

Director Feng······ with just one derivative, differentiated right on the fraction, making Zheng Bang dizzy and confused, parameters skewed to one side. It was as if he had opened a table of elementary functions: squares, roots, everything ticked off and differentiated out. Zheng Iron-Head could not keep up, tossed the answer aside, and only shouted, “Good differentiation!” Director Feng scolded, “Iron-head brat! You still dare to talk back!” He picked up the pen and differentiated the numerator again, sparks flying, heads cracking and bleeding, as if he had opened a binomial theorem: cubic, quartic, quintic terms all burst out.

The people watching on both sides feared Director Feng. Who would dare step forward to stop him.

Zheng Bang could not differentiate it, and begged for mercy. Director Feng shouted, “Ha! You iron-head brat! If you only had the guts to do full case analysis with me, I might spare you! But now you beg me for mercy, and I insist on separating the parameters!” He differentiated once more. On the new function it went straight, like working from a common derivative table: exponentials, logarithms, numerator and denominator ringing together. When the director looked, he saw Zheng Bang collapsed on the ground, only exhaling, not inhaling, unable to move.

Director Feng pretended, “You bastard, playing dead. I will differentiate again!” Then his head gradually disappeared. The director thought, “I only meant to make him pay for one meal. I did not expect three derivatives would really differentiate him to death. I will get points deducted, and there are no more problems to do. Better to leave early.” He walked away, turned back and pointed at the paper, “This useless problem, I skip it!” While calculating, he strode away in big steps.

Translated by ChatGPT 5