الوصف
Helloooo! Can you hear me?
تُعطى لك متتالية $A = (A_1, A_2, \dots, A_N)$ طولها $N$ تتكون من أعداد صحيحة أكبر من أو تساوي $-1$. باستخدام هذه المتتالية ومعامل $c$، قم بإجراء العمليات التالية:
- في البداية، اجعل المتغير $x := 0$.
- لكل $i = 1, 2, \dots, N$، كرر العملية التالية:
- إذا كان $A_i = -1$، فقم بتحديث $x$ إلى $x := \max(0, x - c)$.
- وإلا، فقم بتحديث $x$ إلى $x := x + A_i$.
أجب عن $Q$ من الأسئلة بالشكل التالي:
- عندما يكون المعامل $c = C_i$، أوجد أكبر قيمة يصل إليها $x$ خلال سلسلة العمليات بأكملها.
الإدخال
يحتوي السطر الأول على عددين صحيحين $N$ و $Q$ ($1 \le N, Q \le 3 \times 10^5$). يحتوي السطر الثاني على $N$ من الأعداد الصحيحة $A_i$ ($-1 \le A_i \le 10^6$). يحتوي كل سطر من الأسطر الـ $Q$ التالية على عدد صحيح $C_i$، يمثل قيمة المعامل للسؤال رقم $i$ ($0 \le C_i \le 10^6$).
الإخراج
اطبع $Q$ من الأسطر. في السطر رقم $i$، اطبع الإجابة عن السؤال رقم $i$.
أمثلة
الإدخال 1
20 11 50 100 50 100 0 200 -1 50 100 -1 200 -1 200 0 200 -1 200 200 -1 200 30 60 90 180 270 360 540 200 400 600 0
الإخراج 1
1700 1550 1400 950 570 500 500 850 500 500 1850
ملاحظة
نشرح السؤال الأول من مدخلات المثال الأول:
- في هذا السؤال، المعامل هو $c = 30$.
- في البداية، $x = 0$.
- بما أن $A_1 = 50$، يتم تحديث $x$ إلى $x = 0 + 50 = 50$.
- بما أن $A_2 = 100$، يتم تحديث $x$ إلى $x = 50 + 100 = 150$.
- ...
- بما أن $A_6 = 200$، يتم تحديث $x$ إلى $x = 300 + 200 = 500$.
- بما أن $A_7 = -1$، يتم تحديث $x$ إلى $x = \max(0, 500 - 30) = 470$.
- ...
- بما أن $A_{19} = -1$، يتم تحديث $x$ إلى $x = \max(0, 1530 - 30) = 1500$.
- بما أن $A_{20} = 200$، يتم تحديث $x$ إلى $x = 1500 + 200 = 1700$.
بما في ذلك الأجزاء المحذوفة، فإن أكبر قيمة يصل إليها $x$ خلال سلسلة العمليات بأكملها هي $1700$.