בזמנו הפנוי יצר Farmer John את שירות שיתוף הסרטונים MooTube. הפרות יכולות להקליט, לשתף ולגלות סרטונים משעשעים. הן כבר פרסמו $N$ סרטונים ($1\le N\le100{,}000$), ממוספרים $1\ldots N$, אך FJ לא יודע לעזור להן למצוא חדשים שיאהבו.

הוא רוצה לכל סרטון רשימת ״סרטונים מוצעים״, הממליצה על הקרובים ביותר למה שכבר צופים בו.

FJ מגדיר ״רלוונטיות״ בין סרטונים. הוא בוחר $N-1$ זוגות ומחשב ידנית לכל זוג. הסרטונים הם קודקודי רשת והזוגות נבחרו להתחבר כך שבין כל שני סרטונים מסלול אחד בדיוק. רלוונטיות זוג היא הרלוונטיות המזערית של חיבור במסלול הזה.

FJ בוחר $K$ כדי להציע לצד כל סרטון את כל האחרים עם רלוונטיות לפחות $K$. אבל רבים מדי עלולים להסיח את הפרות מייצור חלב! הוא רוצה לבחור $K$ בקפידה ומבקש תשובות לשאלות על ההצעות עבור ערכי $K$ מסוימים.

קלט

השורה הראשונה מכילה $N,Q$ ($1\le Q\le100{,}000$).

$N-1$ השורות הבאות מתארות זוגות שהושוו ידנית. השלמים $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) מציינים חיבור בין $p_i,q_i$ ברלוונטיות $r_i$.

$Q$ השורות הבאות הן שאלות. השלמים $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) שואלים בשאלה $i$ כמה סרטונים יוצעו לצופי $v_i$ אם $K=k_i$.

פלט

הדפיסו $Q$ שורות; שורה $i$ עונה לשאלה $i$.

דוגמאות

קלט 1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

פלט 1

3
0
2

הסבר

הרלוונטיות של $1,2$, של $2,3$, של $2,4$ היא $3,2,4$. לכן של $1,3$, של $1,4$, של $3,4$ היא $\min(3,2)=2$, $\min(3,4)=3$, $\min(2,4)=2$.

FJ שואל על סרטון $2$ כאשר $K=1$, על $1$ כאשר $K=3$ ועל $1$ כאשר $K=4$. כאשר $K=1$, $2$ מציע $1,3,4$; כאשר $K=4$, $1$ לא מציע כלום; כאשר $K=3$, $1$ מציע $2,4$.

מחבר הבעיה: Jay Leeds