يلعب شياو Q مع الحاسوب لعبة بطاقات تبادلية الأدوار تُسمى "الدفاع المطلق".

يمتلك شياو Q رزمة بطاقات بحجم $n$، وتحتوي على نوعين من البطاقات: بطاقات هجوم وبطاقات دفاع. عند بدء اللعبة، يسحب شياو Q $k \ (1 \le k \le n)$ بطاقة من أعلى الرزمة لتكون يده الابتدائية، ثم يدخل في عدة جولات مواجهة مع الحاسوب.

في بداية كل جولة مواجهة، يسحب شياو Q $2$ بطاقة من أعلى الرزمة. وبشكل خاص، إذا تبقت بطاقة واحدة فقط في الرزمة، فإنه يسحب بطاقة واحدة فقط. تنقسم كل جولة مواجهة إلى دورين:

• الدور الأول: يكون شياو Q هو المهاجم، والحاسوب هو المدافع؛
• الدور الثاني: يكون شياو Q هو المدافع، والحاسوب هو المهاجم.

في كل دور، يجب على المهاجم أن يلعب بطاقة هجوم واحدة من يده للهجوم، ويجب على المدافع أن يلعب بطاقة دفاع واحدة من يده للدفاع. من لا يستطيع اللعب حسب المتطلبات يُعتبر خاسرًا فورًا.

يمتلك الحاسوب عددًا لا نهائيًا من بطاقات الهجوم والدفاع، أي أنه يمكنه دائمًا لعب البطاقة المطلوبة في كل دور. ولتحقيق التوازن مع قوة الحاسوب، يستطيع شياو Q استخدام مهارة خاصة: عندما يكون شياو Q مدافعًا، يمكنه لعب بطاقة هجوم واحدة من يده للدفاع بدلًا من بطاقة الدفاع. يمكن استخدام هذه المهارة مرة واحدة كل $3$ جولات مواجهة فقط، أي بعد استخدامها في جولة معينة، لا يمكن استخدامها في الجولتين التاليتين.

الهدف من الفوز لشياو Q حسب القواعد هو البقاء على قيد الحياة أمام الهجمات الشرسة من الحاسوب، أي أن توجد جولة تنتهي ويكون الرزمة قد نفذت تمامًا. بشكل خاص، إذا كانت الرزمة فارغة عند بدء اللعبة، يحقق شياو Q هدف الفوز مباشرة. يرغب شياو Q في معرفة الحد الأدنى لعدد البطاقات الابتدائية $k$ اللازمة لتحقيق هدف الفوز.

شعر شياو Q أن هذه المسألة بسيطة جدًا، لذا أضاف $q$ تعديلات على الرزمة. في التعديل رقم $i \ (1 \le i \le q)$، يُعطى عدد صحيح موجب $x_i$، ويُغير نوع البطاقة رقم $x_i$ (من أعلى الرزمة إلى الأسفل)، أي تحويل بطاقة هجوم إلى دفاع أو العكس. عليك إيجاد الحد الأدنى لعدد البطاقات الابتدائية $k$ لتحقيق هدف الفوز لشياو Q بعد كل تعديل، بما في ذلك الحالة الابتدائية.

تنسيق الإدخال

يُقرأ الإدخال من المعيار القياسي.

تحتوي هذه المسألة على عدة مجموعات من بيانات الاختبار.

السطر الأول يحتوي على عددين صحيحين غير سالبين $c, t$، يمثلان رقم نقطة الاختبار وعدد مجموعات بيانات الاختبار على التوالي. $c = 0$ تعني أن هذه نقطة اختبار نموذجية (مثال).

بعد ذلك، لكل مجموعة من بيانات الاختبار:

السطر الأول يحتوي على عددين صحيحين غير سالبين $n, q$، يمثلان حجم الرزمة وعدد التعديلات.

السطر الثاني يحتوي على سلسلة من الأحرف بطول $n$، $s_1 \dots s_n$، تمثل كل بطاقة من أعلى الرزمة إلى الأسفل، حيث $s_i = 0$ تعني أن البطاقة $i$ هي بطاقة هجوم، و$s_i = 1$ تعني أنها بطاقة دفاع.

السطر $(i + 2) \ (1 \le i \le q)$ يحتوي على عدد صحيح موجب $x_i$، ويمثل البطاقة رقم $x_i$ (من الأعلى إلى الأسفل) التي سيتم تعديل نوعها في التعديل رقم $i$.

تنسيق الإخراج

يُطبع الإخراج إلى المعيار القياسي.

لكل مجموعة بيانات اختبار، إذا كان الجواب الابتدائي $k_0$، وبعد كل تعديل رقم $i \ (1 \le i \le q)$ يكون الجواب $k_i$، عليك طباعة سطر واحد يحتوي على $q + 1$ عددًا صحيحًا $k_0, k_1, \dots, k_q$، تمثل الحد الأدنى لعدد البطاقات الابتدائية المطلوبة لتحقيق هدف الفوز في كل حالة (الابتدائية وبعد كل تعديل).

عينة

الإدخال

0 3
5 1
01010
4
7 0
0001000
10 0
0001010000

الإخراج

1 1
3
2

الشرح

تحتوي هذه العينة على ثلاث مجموعات بيانات اختبار.

بالنسبة للمجموعة الأولى:

• الحالة الابتدائية: الرزمة هي $01010$. إذا كان عدد البطاقات الابتدائية $1$، فإن إحدى طرق اللعب الممكنة لـشياو Q هي:

  • في البداية، يده تحتوي على ${0}$؛
  • يسحب من الرزمة بطاقتين، يلعب بطاقة هجوم وبطاقة دفاع، تبقى في يده ${0}$؛
  • يسحب بطاقتين، يلعب بطاقة هجوم وبطاقة دفاع، تبقى في يده ${0}$، وتنتهي الرزمة هنا.

  بما أنه يجب سحب بطاقة واحدة على الأقل كبداية، فالحد الأدنى هو $1$، إذن $k_0 = 1$.

• بعد التعديل الأول، تصبح الرزمة $01000$. إذا كان عدد البطاقات الابتدائية $1$، فإن إحدى طرق اللعب الممكنة:

  • في البداية، يده تحتوي على ${0}$؛
  • يسحب بطاقتين، يلعب بطاقة هجوم وبطاقة دفاع، تبقى في يده ${0}$؛
  • يسحب بطاقتين، يلعب بطاقة هجوم، ويستخدم المهارة الخاصة ليلعب بطاقة هجوم كدفاع، تبقى في يده ${0}$، وتنتهي الرزمة هنا.

  إذن، $k_1 = 1$.

بالنسبة للمجموعة الثانية:

إذا كان عدد البطاقات الابتدائية $3$، فإن إحدى طرق اللعب الممكنة:

• في البداية، يده ${0, 0, 0}$؛
• يسحب بطاقتين، يلعب بطاقة هجوم وبطاقة دفاع، يده ${0, 0, 0}$؛
• يسحب بطاقتين، يلعب بطاقة هجوم، ويستخدم المهارة الخاصة ليلعب بطاقة هجوم كدفاع، يده ${0, 0, 0}$، وتنتهي الرزمة.

يمكن إثبات أنه لا يوجد عدد أقل من $3$ كبداية يمكن به إنهاء الرزمة، إذًا الجواب هو $3$.

بالنسبة للمجموعة الثالثة:

إذا كان عدد البطاقات الابتدائية $2$، فإن إحدى طرق اللعب الممكنة:

• في البداية، يده ${0, 0}$؛
• يسحب بطاقتين، يلعب بطاقة هجوم ويستخدم المهارة الخاصة ليلعب بطاقة هجوم كدفاع، يده ${0, 1}$؛
• يسحب بطاقتين، يلعب بطاقة هجوم وبطاقة دفاع، يده ${0, 1}$؛
• يسحب بطاقتين، يلعب بطاقة هجوم وبطاقة دفاع، يده ${0, 0}$؛
• يسحب بطاقتين، يلعب بطاقة هجوم ويستخدم المهارة الخاصة ليلعب بطاقة هجوم كدفاع، يده ${0, 0}$، وتنتهي الرزمة.

يمكن إثبات أنه لا يوجد عدد أقل من $2$ كبداية يمكن به إنهاء الرزمة، إذًا الجواب هو $2$.

العينة الثانية

انظر إلى ex_2.in و ex_2.ans في دليل التنزيل.

تُحقق هذه العينة شروط نقطة الاختبار $2$.

العينة الثالثة

انظر إلى ex_3.in و ex_3.ans في دليل التنزيل.

تُحقق هذه العينة شروط نقاط الاختبار $5\sim 7$.

العينة الرابعة

انظر إلى ex_4.in و ex_4.ans في دليل التنزيل.

تُحقق هذه العينة شروط نقاط الاختبار $9, 10$.

العينة الخامسة

انظر إلى ex_5.in و ex_5.ans في دليل التنزيل.

تُحقق هذه العينة شروط نقطة الاختبار $11$.

العينة السادسة

انظر إلى ex_6.in و ex_6.ans في دليل التنزيل.

تُحقق هذه العينة شروط نقاط الاختبار $12\sim 14$.

حدود البيانات

ليكن $N, Q$ هما مجموع قيم $n, q$ في كل نقطة اختبار واحدة. لجميع بيانات الاختبار، يُضمن:

• $1 \le t \le 10^{4}$؛
• $1 \le n \le 2 \times 10^{5}$، $N \le 5 \times 10^{5}$؛
• $0 \le q \le 2 \times 10^{5}$، $Q \le 5 \times 10^{5}$؛
• لكل $1 \le i \le n$، يكون $s_i \in {0, 1}$؛
• لكل $1 \le i \le q$، يكون $1 \le x_i \le n$.

خاصية خاصة A: يُضمن لكل $1 \le i \le n$ أن $s_i$ تُولّد بشكل مستقل وعشوائي منتظم من ${0, 1}$.

خاصية خاصة B: يُضمن أن كل $x_i$ مختلف، ولكل $1 \le i \le q$، $s_{x_i} = 1$.

خاصية خاصة C: يُضمن أن كل $x_i$ مختلف، ولكل $1 \le i \le q$، $s_{x_i} = 0$.

خاصية خاصة D: يُضمن أن كل $x_i$ يُختار بشكل مستقل وعشوائي منتظم من $[1, n]$.

خاصية خاصة E: يُضمن لكل $0 \le i \le q$، $1\le k_i \le 45$.