أمام Yuki ممر مشاة غريب.

يمكن النظر إلى هذا الممر على أنه شجرة ذات $n$ عقد. تصل الحافة رقم $i$ بين العقدة $u_i$ والعقدة $v_i$. كل عقدة ملوّنة إما بالأسود أو بالأبيض، ويصف ذلك نص ثنائي $s$ طوله $n$:

• إذا كان $s_i=0$، فلون العقدة $i$ أسود.

• إذا كان $s_i=1$، فلون العقدة $i$ أبيض.

لدى Yuki قدرة قفز $k$، أي إنها عندما تكون عند العقدة $x$ تستطيع القفز إلى أي عقدة $y$ تحقق $\operatorname{dist}(x,y)\le k$. هنا، تمثّل $\operatorname{dist}(x,y)$ عدد الحواف على المسار البسيط بين العقدتين $x$ و$y$.

بعد ذلك، ستنفّذ Yuki عددًا من جولات القفز على الممر يساوي $n-1$. في الجولة رقم $i$، تبدأ من العقدة $1$ وتريد الوصول إلى العقدة $i+1$ عبر سلسلة من القفزات. وفي الوقت نفسه، تريد تقليل عدد مرات هبوطها على عقدة سوداء بعد قفزاتها.

عليك مساعدة Yuki في إيجاد أقل عدد من مرات الهبوط على عقدة سوداء لكل جولة من جولات القفز.

الإدخال

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

يحتوي السطر الأول على عدد صحيح موجب $t$ ($1\le t\le 10^5$)، يمثّل عدد حالات الاختبار.

لكل حالة اختبار:

• يحتوي السطر الأول على عددين صحيحين موجبين $n,k$ ($1\le n\le 5\cdot 10^5$، $1\le k\le n$).

• يحتوي السطر الثاني على نص ثنائي $s$ طوله $n$ ($s_i\in\{0,1\}$).

• يحتوي كل من الأسطر التالية وعددها $n-1$ على عددين صحيحين موجبين $u_i,v_i$ ($1\le u_i,v_i\le n$، $u_i\ne v_i$).

يُضمن أن مجموع $n$ على جميع حالات الاختبار لا يتجاوز $5\cdot 10^5$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على $n-1$ عددًا صحيحًا، حيث يمثّل العدد رقم $i$ أقل عدد من مرات هبوط Yuki على عقدة سوداء خلال جولة القفز رقم $i$.

أمثلة

الإدخال 1

2
5 1
01010
3 5
2 1
1 3
3 4
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9

الإخراج 1

0 1 1 2
1 1 1 0 1 1 1 2

ملاحظة

بالنسبة إلى حالة الاختبار الأولى:

• في جولة القفز رقم $1$، إحدى سلاسل العقد المزارة الصحيحة هي $1,2$.

• في جولة القفز رقم $4$، إحدى سلاسل العقد المزارة الصحيحة هي $1,3,5$.

بالنسبة إلى حالة الاختبار الثانية:

• في جولة القفز رقم $4$، إحدى سلاسل العقد المزارة الصحيحة هي $1,5$.

• في جولة القفز رقم $7$، إحدى سلاسل العقد المزارة الصحيحة هي $1,5,8$.

• في جولة القفز رقم $8$، إحدى سلاسل العقد المزارة الصحيحة هي $1,4,9$.