• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

آرایه‌ای متشکل از \(n\) عدد داریم. یک بازه از این اعداد را زیبا می‌نامیم اگر و تنها اگر مجموع اعداد حاضر در این بازه کمتر یا مساوی عدد \(k\) و بیشتر یا مساوی عدد \(-k\) باشد. به عبارتی دیگر، قدر مطلق مجموع اعداد این بازه باید حداکثر \(k\) باشد.

روی این آرایه \(q\) بار عملیات انجام شده است، هر عملیات به این صورت است که دو عدد \(i\) و \(x\) مشخص شده‌اند (\(1 \le i \le n-1\))، سپس عضو \(i\)-ام آرایه با عدد \(x\) جمع می‌شود و از عضو \(i+1\)-ام آرایه عدد \(x\) تفریق می‌شود. (توجه کنید که مقدار \(x\) می‌تواند منفی هم باشد)

از شما خواسته شده یکبار در ابتدا و سپس بعد از اعمال هر عملیات، تعداد بازه‌های زیبای آرایه را محاسبه کنید.

دقت کنید تمامی عملیات‌ها پایا هستند، یعنی اثر آن‌ها در عملیات‌های بعدی نیز روی آرایه می‌ماند.

ورودی

در خط اول ورودی به ترتیب سه عدد \(n\)، \(k\) و \(q\) آمده‌اند. در خط دوم \(n\) عدد آمده‌اند که اعداد اولیه‌ی آرایه هستند و عدد \(i\) را با \(a_i\) نمایش می‌دهیم. در \(q\) خط بعدی، در هر خط به ترتیب دو عدد \(i\) و \(x\) آمده‌اند که عملیات را مشخص می‌کنند.

\[ 2 \le n \le 100 \, 000 \] \[ 1 \le q \le 100 \, 000 \] \[ 0 \le k \le 10 ^ 9\] \[ -10 ^ 9 \le a_i, x \le 10 ^ 9\] \[ 1 \le i \le n - 1 \]

همچنین تضمین می‌شود قدر مطلق تمامی اعداد آرایه بعد از هر کوئری حداکثر \(10^9\) خواهد ماند.

خروجی

خروجی شما باید شامل \(q+1\) خط باشد که نشان دهد در ابتدا و بعد از انجام هر عملیات تعداد بازه‌های زیبای آرایه چقدر است.

مثال

ورودی نمونه ۱

5 3 2
1 2 3 4 5 
3 -2
2 4

خروجی نمونه ۱

4
5
4

در این نمونه در ابتدا بازه‌های \([1]\)، \([2]\)، \([3]\) و \([1,2]\) زیبا هستند.

بعد از عملیات اول آرایه تبدیل می‌شود به: \(1, 2, 1, 6, 5\). بعد از این تغییر بازه‌های \([1]\)، \([2]\)، \([3]\)، \([1,2]\) و \([2,3]\) زیبا خواهند بود.

بعد از عملیات دوم آرایه به این صورت خواهد بود: \(1, 6, -3, 6, 5\). بعد از این تغییر بازه‌های \([1]\)، \([3]\)، \([2,3]\) و \([3,4]\) زیبا هستند.

(منظور از بازه‌ی \([i,j]\) بازه‌ای است که از عضو \(i\)ام شروع شده و تا عضو \(j\)ام ادامه دارد)

ورودی نمونه ۲

5 5 5
-3 -4 0 5 -5 
2 1
2 3
4 -4
2 -1
3 5

خروجی نمونه ۲

12
12
13
12
12
13

ورودی نمونه ۳

7 5 10
-10 11 -15 -8 6 8 8 
2 -16
6 -7
2 13
2 -18
4 -6
3 -8
4 10
5 7
2 -2
6 17

خروجی نمونه ۳

6
7
10
8
9
8
6
10
8
7
7